home *** CD-ROM | disk | FTP | other *** search
/ PSION CD 2 / PsionCDVol2.iso / Programs / 876 / hugs.sis / Sequence.hs < prev    next >
Encoding:
Text File  |  2000-09-21  |  3.1 KB  |  103 lines
  1. module Sequence(
  2.     Sequence( fromList, toList ),
  3.     -- instances for [], Maybe and List
  4.     List -- same instances as for []
  5.     ) where
  6.  
  7. import Maybe(maybeToList, listToMaybe)
  8. import Monad
  9.  
  10. class (Functor m, MonadPlus m) => Sequence m where
  11.   fromList :: [a] -> m a
  12.   toList   :: m a -> [a]
  13.  
  14.   fromList = msum . fmap return
  15.  
  16. ----------------------------------------------------------------
  17. -- []: fast access to head but slow append
  18. ----------------------------------------------------------------
  19.  
  20. instance Sequence [] where
  21.   fromList = id
  22.   toList   = id
  23.  
  24. ----------------------------------------------------------------
  25. -- Maybe: single element lists - sort of
  26. ----------------------------------------------------------------
  27.  
  28. instance Sequence Maybe where
  29.   toList   = maybeToList
  30.   fromList = listToMaybe
  31.  
  32. ----------------------------------------------------------------
  33. -- List: lists with fast append (but slower indexing!)
  34. ----------------------------------------------------------------
  35.  
  36. -- Instead of providing Cons as a constructor, we provide Append.
  37.  
  38. data List a = Empty
  39.              | Singleton a
  40.              | Append (List a) (List a)
  41.  
  42. -- We define all the same instances that are defined for [].
  43.  
  44. -- The following definitions are independent of the choice of
  45. -- representation since there's very little benefit in writing
  46. -- representation-dependent versions.
  47.  
  48. instance Eq a => Eq (List a) where
  49.   xs == ys = toList xs == toList ys
  50.  
  51. instance Ord a => Ord (List a) where
  52.   compare xs ys = compare (toList xs) (toList ys)
  53.  
  54. instance Read a => Read (List a) where
  55.   readsPrec p s = [ (fromList xs, r)      | (xs,  r) <- readsPrec p s ]
  56.   readList    s = [ (map fromList xss, r) | (xss, r) <- readList    s ] 
  57.  
  58. instance Show a => Show (List a) where
  59.   showsPrec p xs  = showsPrec p (toList xs)
  60.   showList    xss = showList    (map toList xss)
  61.  
  62. -- The following operations are representation dependent and ought
  63. -- to go much faster than any alternative way of writing them.
  64. --
  65. -- For example, the monadic operators preserve the structure of their
  66. -- input.
  67.  
  68. instance Functor List where
  69.   fmap f Empty          = Empty
  70.   fmap f (Singleton x)  = Singleton (f x)
  71.   fmap f (Append xs ys) = Append (fmap f xs) (fmap f ys)
  72.  
  73. instance Monad List where
  74.   Empty        >>= k = Empty
  75.   Singleton x  >>= k = k x
  76.   Append xs ys >>= k = Append (xs >>= k) (ys >>= k)
  77.  
  78.   return = Singleton
  79.  
  80. instance MonadPlus List where
  81.   mzero = Empty
  82.   mplus = Append
  83.  
  84. instance Sequence List where
  85.   fromList = foldr (\ x xs -> Singleton x `Append` xs) Empty
  86.  
  87.   toList xs = flatten xs []
  88.    where
  89.     -- flatten uses the standard technique of a "work list" yss
  90.     -- flatten xs yss = xs ++ concatMap toList yss
  91.     -- flatten :: List a -> [List a] -> [a]
  92.     flatten Empty          []       = []
  93.     flatten Empty          (ys:yss) = flatten ys yss
  94.     flatten (Singleton x)  []       = [x]
  95.     flatten (Singleton x)  (ys:yss) = x : flatten ys yss
  96.  
  97.     -- special cases for extra speed
  98.     flatten (Append (Singleton x) ys) yss = x:flatten ys yss
  99.     flatten (Append xs Empty) yss   = flatten xs yss
  100.     flatten (Append Empty ys) yss   = flatten ys yss
  101.  
  102.     flatten (Append xs ys) yss      = flatten xs (ys:yss)
  103.