stream-fusion 0.1.1 → 0.1.2
raw patch · 3 files changed
+152/−162 lines, 3 files
Files
- Data/List/Stream.hs +121/−132
- Data/Stream.hs +16/−28
- stream-fusion.cabal +15/−2
Data/List/Stream.hs view
@@ -10,20 +10,13 @@ -- -- A reimplementation of the standard Haskell list library to take advantage of -- stream fusion, and new GHC optimisations. The fusion mechanism is--- based on stream fusion for sequences. Described in: ------ * /Stream Fusion: From Lists to Streams to Nothing at All/, by--- Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007.--- <http://www.cse.unsw.edu.au/~dons/papers/CLS07.html>+-- based on that described in: ----- * /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and+-- /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and -- Roman Leshchinskiy, Practical Aspects of Declarative Languages -- 8th International Symposium, PADL 2007, 2007.--- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html> ----- See the source for the complete story:------ * <http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs>+-- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html> -- -- This library is a drop in replacement for "Data.List". --@@ -389,8 +382,8 @@ {-# RULES "head -> fusible" [~1] forall xs. head xs = Stream.head (stream xs)-"head -> unfused" [1] forall xs.- Stream.head (stream xs) = head xs+--"head -> unfused" [1] forall xs.+-- Stream.head (stream xs) = head xs #-} -- | /O(n)/, /fusion/. Extract the last element of a list, which must be finite@@ -406,8 +399,8 @@ {-# RULES "last -> fusible" [~1] forall xs. last xs = Stream.last (stream xs)-"last -> unfused" [1] forall xs.- Stream.last (stream xs) = last xs+--"last -> unfused" [1] forall xs.+-- Stream.last (stream xs) = last xs #-} -- | /O(1)/, /fusion/. Extract the elements after the head of a list, which@@ -420,8 +413,8 @@ {-# RULES "tail -> fusible" [~1] forall xs. tail xs = unstream (Stream.tail (stream xs))-"tail -> unfused" [1] forall xs.- unstream (Stream.tail (stream xs)) = tail xs+--"tail -> unfused" [1] forall xs.+-- unstream (Stream.tail (stream xs)) = tail xs #-} -- | /O(n)/, /fusion/. Return all the elements of a list except the last one.@@ -437,8 +430,8 @@ {-# RULES "init -> fusible" [~1] forall xs. init xs = unstream (Stream.init (stream xs))-"init -> unfused" [1] forall xs.- unstream (Stream.init (stream xs)) = init xs+--"init -> unfused" [1] forall xs.+-- unstream (Stream.init (stream xs)) = init xs #-} -- | /O(1)/, /fusion/. Test whether a list is empty.@@ -450,8 +443,8 @@ {-# RULES "null -> fusible" [~1] forall xs. null xs = Stream.null (stream xs)-"null -> unfused" [1] forall xs.- Stream.null (stream xs) = null xs+--"null -> unfused" [1] forall xs.+-- Stream.null (stream xs) = null xs #-} -- | /O(n)/, /fusion/. 'length' returns the length of a finite list as an 'Int'.@@ -470,8 +463,8 @@ {-# RULES "length -> fusible" [~1] forall xs. length xs = Stream.length (stream xs)-"length -> unfused" [1] forall xs.- Stream.length (stream xs) = length xs+--"length -> unfused" [1] forall xs.+-- Stream.length (stream xs) = length xs #-} -- ---------------------------------------------------------------------@@ -499,8 +492,8 @@ {-# RULES "map -> fusible" [~1] forall f xs. map f xs = unstream (Stream.map f (stream xs))-"map -> unfused" [1] forall f xs.- unstream (Stream.map f (stream xs)) = map f xs+--"map -> unfused" [1] forall f xs.+-- unstream (Stream.map f (stream xs)) = map f xs #-} -- | /O(n)/, /fusion/. 'reverse' @xs@ returns the elements of @xs@ in reverse order.@@ -629,25 +622,23 @@ {-# RULES "foldl -> fusible" [~1] forall f z xs. foldl f z xs = Stream.foldl f z (stream xs)-"foldl -> unfused" [1] forall f z xs.- Stream.foldl f z (stream xs) = foldl f z xs+--"foldl -> unfused" [1] forall f z xs.+-- Stream.foldl f z (stream xs) = foldl f z xs #-} -- | /O(n)/, /fusion/. A strict version of 'foldl'. foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f z0 xs0 = go z0 xs0-#ifndef __HADDOCK__ where go !z [] = z go !z (x:xs) = go (f z x) xs-#endif {-# INLINE [1] foldl' #-} {-# RULES "foldl' -> fusible" [~1] forall f z xs. foldl' f z xs = Stream.foldl' f z (stream xs)-"foldl' -> unfused" [1] forall f z xs.- Stream.foldl' f z (stream xs) = foldl' f z xs+--"foldl' -> unfused" [1] forall f z xs.+-- Stream.foldl' f z (stream xs) = foldl' f z xs #-} -- | /O(n)/, /fusion/. 'foldl1' is a variant of 'foldl' that has no starting value argument,@@ -663,26 +654,24 @@ {-# RULES "foldl1 -> fusible" [~1] forall f xs. foldl1 f xs = Stream.foldl1 f (stream xs)-"foldl1 -> unfused" [1] forall f xs.- Stream.foldl1 f (stream xs) = foldl1 f xs+--"foldl1 -> unfused" [1] forall f xs.+-- Stream.foldl1 f (stream xs) = foldl1 f xs #-} -- | /O(n)/, /fusion/. A strict version of 'foldl1' foldl1' :: (a -> a -> a) -> [a] -> a foldl1' _ [] = errorEmptyList "foldl1'" foldl1' f (x0:xs0) = go x0 xs0-#ifndef __HADDOCK__ where go !z [] = z go !z (x:xs) = go (f z x) xs-#endif {-# INLINE [1] foldl1' #-} {-# RULES "foldl1' -> fusible" [~1] forall f xs. foldl1' f xs = Stream.foldl1' f (stream xs)-"foldl1 -> unfused" [1] forall f xs.- Stream.foldl1' f (stream xs) = foldl1' f xs+--"foldl1 -> unfused" [1] forall f xs.+-- Stream.foldl1' f (stream xs) = foldl1' f xs #-} -- | /O(n)/, /fusion/. 'foldr', applied to a binary operator, a starting value (typically@@ -703,8 +692,8 @@ {-# RULES "foldr -> fusible" [~1] forall f z xs. foldr f z xs = Stream.foldr f z (stream xs)-"foldr -> unfused" [1] forall f z xs.- Stream.foldr f z (stream xs) = foldr f z xs+--"foldr -> unfused" [1] forall f z xs.+-- Stream.foldr f z (stream xs) = foldr f z xs #-} -- | /O(n)/, /fusion/. 'foldr1' is a variant of 'foldr' that has no starting value argument,@@ -719,8 +708,8 @@ {-# RULES "foldr1 -> fusible" [~1] forall f xs. foldr1 f xs = Stream.foldr1 f (stream xs)-"foldr1 -> unfused" [1] forall f xs.- Stream.foldr1 f (stream xs) = foldr1 f xs+--"foldr1 -> unfused" [1] forall f xs.+-- Stream.foldr1 f (stream xs) = foldr1 f xs #-} -- ---------------------------------------------------------------------@@ -744,8 +733,8 @@ {-# RULES "concat -> fused" [~1] forall xs. concat xs = Stream.concat (stream xs)-"concat -> unfused" [1] forall xs.- Stream.concat (stream xs) = concat xs+--"concat -> unfused" [1] forall xs.+-- Stream.concat (stream xs) = concat xs #-} -- | /O(n)/, /fusion/. Map a function over a list and concatenate the results.@@ -783,8 +772,8 @@ {-# RULES "and -> fused" [~1] forall xs. and xs = Stream.and (stream xs)-"and -> unfused" [1] forall xs.- Stream.and (stream xs) = and xs+--"and -> unfused" [1] forall xs.+-- Stream.and (stream xs) = and xs #-} -- | /O(n)/, /fusion/. 'or' returns the disjunction of a Boolean list. For the result to be@@ -799,8 +788,8 @@ {-# RULES "or -> fused" [~1] forall xs. or xs = Stream.or (stream xs)-"or -> unfused" [1] forall xs.- Stream.or (stream xs) = or xs+--"or -> unfused" [1] forall xs.+-- Stream.or (stream xs) = or xs #-} -- | /O(n)/, /fusion/. Applied to a predicate and a list, 'any' determines if any element@@ -819,8 +808,8 @@ {-# RULES "any -> fusible" [~1] forall f xs. any f xs = Stream.any f (stream xs)-"any -> unfused" [1] forall f xs.- Stream.any f (stream xs) = any f xs+--"any -> unfused" [1] forall f xs.+-- Stream.any f (stream xs) = any f xs #-} -- | Applied to a predicate and a list, 'all' determines if all elements@@ -836,8 +825,8 @@ {-# RULES "all -> fusible" [~1] forall f xs. all f xs = Stream.all f (stream xs)-"all -> unfused" [1] forall f xs.- Stream.all f (stream xs) = all f xs+--"all -> unfused" [1] forall f xs.+-- Stream.all f (stream xs) = all f xs #-} -- | /O(n)/, /fusion/. The 'sum' function computes the sum of a finite list of numbers.@@ -866,15 +855,15 @@ {-# RULES "sum -> fusible" [~1] forall xs. sum xs = Stream.sum (stream xs)-"sum -> unfused" [1] forall xs.- Stream.sum (stream xs) = sum xs+--"sum -> unfused" [1] forall xs.+-- Stream.sum (stream xs) = sum xs #-} {-# RULES "sumInt -> fusible" [~1] forall (xs :: [Int]). sumInt xs = Stream.sum (stream xs)-"sumInt -> unfused" [1] forall (xs :: [Int]).- Stream.sum (stream xs) = sumInt xs+--"sumInt -> unfused" [1] forall (xs :: [Int]).+-- Stream.sum (stream xs) = sumInt xs #-} -- | /O(n)/,/fusion/. The 'product' function computes the product of a finite list of numbers.@@ -903,15 +892,15 @@ {-# RULES "product -> fused" [~1] forall xs. product xs = Stream.product (stream xs)-"product -> unfused" [1] forall xs.- Stream.product (stream xs) = product xs+--"product -> unfused" [1] forall xs.+-- Stream.product (stream xs) = product xs #-} {-# RULES "productInt -> fusible" [~1] forall (xs :: [Int]). productInt xs = Stream.product (stream xs)-"productInt -> unfused" [1] forall (xs :: [Int]).- Stream.product (stream xs) = productInt xs+--"productInt -> unfused" [1] forall (xs :: [Int]).+-- Stream.product (stream xs) = productInt xs #-} -- | /O(n)/,/fusion/. 'maximum' returns the maximum value from a list,@@ -926,8 +915,8 @@ {-# RULES "maximum -> fused" [~1] forall xs. maximum xs = Stream.maximum (stream xs)-"maximum -> unfused" [1] forall xs.- Stream.maximum (stream xs) = maximum xs+--"maximum -> unfused" [1] forall xs.+-- Stream.maximum (stream xs) = maximum xs #-} -- We can't make the overloaded version of maximum strict without@@ -947,8 +936,8 @@ {-# RULES "strictMaximum -> fused" [~1] forall xs. maximum xs = Stream.strictMaximum (stream xs)-"strictMaximum -> unfused" [1] forall xs.- Stream.strictMaximum (stream xs) = strictMaximum xs+--"strictMaximum -> unfused" [1] forall xs.+-- Stream.strictMaximum (stream xs) = strictMaximum xs #-} -- | /O(n)/,/fusion/. 'minimum' returns the minimum value from a list,@@ -963,8 +952,8 @@ {-# RULES "minimum -> fused" [~1] forall xs. minimum xs = Stream.minimum (stream xs)-"minimum -> unfused" [1] forall xs.- Stream.minimum (stream xs) = minimum xs+--"minimum -> unfused" [1] forall xs.+-- Stream.minimum (stream xs) = minimum xs #-} {-# RULES@@ -980,8 +969,8 @@ {-# RULES "strictMinimum -> fused" [~1] forall xs. maximum xs = Stream.strictMinimum (stream xs)-"strictMinimum -> unfused" [1] forall xs.- Stream.strictMinimum (stream xs) = strictMinimum xs+--"strictMinimum -> unfused" [1] forall xs.+-- Stream.strictMinimum (stream xs) = strictMinimum xs #-} -- ---------------------------------------------------------------------@@ -1018,8 +1007,8 @@ {-# RULES "scanl -> fusible" [~1] forall f z xs. scanl f z xs = unstream (Stream.scanl f z (Stream.snoc (stream xs) bottom))-"scanl -> unfused" [1] forall f z xs.- unstream (Stream.scanl f z (Stream.snoc (stream xs) bottom)) = scanl f z xs+--"scanl -> unfused" [1] forall f z xs.+-- unstream (Stream.scanl f z (Stream.snoc (stream xs) bottom)) = scanl f z xs #-} -- | /O(n)/,/fusion/. 'scanl1' is a variant of 'scanl' that has no starting value argument:@@ -1034,8 +1023,8 @@ {-# RULES "scanl1 -> fusible" [~1] forall f xs. scanl1 f xs = unstream (Stream.scanl1 f (Stream.snoc (stream xs) bottom))-"scanl1 -> unfused" [1] forall f xs.- unstream (Stream.scanl1 f (Stream.snoc (stream xs) bottom)) = scanl1 f xs+--"scanl1 -> unfused" [1] forall f xs.+-- unstream (Stream.scanl1 f (Stream.snoc (stream xs) bottom)) = scanl1 f xs #-} @@ -1109,8 +1098,8 @@ {-# RULES "iterate -> fusible" [~1] forall f x. iterate f x = unstream (Stream.iterate f x)-"iterate -> unfused" [1] forall f x.- unstream (Stream.iterate f x) = iterate f x+--"iterate -> unfused" [1] forall f x.+-- unstream (Stream.iterate f x) = iterate f x #-} -- | /fusion/. 'repeat' @x@ is an infinite list, with @x@ the value of every element.@@ -1121,8 +1110,8 @@ {-# RULES "repeat -> fusible" [~1] forall x. repeat x = unstream (Stream.repeat x)-"repeat -> unfused" [1] forall x.- unstream (Stream.repeat x) = repeat x+--"repeat -> unfused" [1] forall x.+-- unstream (Stream.repeat x) = repeat x #-} -- | /O(n)/, /fusion/. 'replicate' @n x@ is a list of length @n@ with @x@ the value of@@ -1141,8 +1130,8 @@ {-# RULES "replicate -> fusible" [~1] replicate = \n x -> unstream (Stream.replicate n x)-"replicate -> unfused" [1] forall n x.- unstream (Stream.replicate n x) = replicate n x+--"replicate -> unfused" [1] forall n x.+-- unstream (Stream.replicate n x) = replicate n x #-} -- | /fusion/. 'cycle' ties a finite list into a circular one, or equivalently,@@ -1160,8 +1149,8 @@ {-# RULES "cycle -> fusible" [~1] forall xs. cycle xs = unstream (Stream.cycle (stream xs))-"cycle -> unfused" [1] forall xs.- unstream (Stream.cycle (stream xs)) = cycle xs+--"cycle -> unfused" [1] forall xs.+-- unstream (Stream.cycle (stream xs)) = cycle xs #-} -- ---------------------------------------------------------------------@@ -1201,8 +1190,8 @@ {-# RULES "unfoldr -> fusible" [~1] forall f x. unfoldr f x = unstream (Stream.unfoldr f x)-"unfoldr -> unfused" [1] forall f x.- unstream (Stream.unfoldr f x) = unfoldr f x+--"unfoldr -> unfused" [1] forall f x.+-- unstream (Stream.unfoldr f x) = unfoldr f x #-} ------------------------------------------------------------------------@@ -1235,8 +1224,8 @@ {-# RULES "take -> fusible" [~1] forall n x. take n x = unstream (Stream.take n (stream x))-"take -> unfused" [1] forall n x.- unstream (Stream.take n (stream x)) = take n x+--"take -> unfused" [1] forall n x.+-- unstream (Stream.take n (stream x)) = take n x #-} {-@@ -1283,8 +1272,8 @@ {-# RULES "drop -> fusible" [~1] forall n x. drop n x = unstream (Stream.drop n (stream x))-"drop -> unfused" [1] forall n x.- unstream (Stream.drop n (stream x)) = drop n x+--"drop -> unfused" [1] forall n x.+-- unstream (Stream.drop n (stream x)) = drop n x #-} -- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of@@ -1326,8 +1315,8 @@ {-# RULES "splitAt -> fusible" [~1] forall n xs. splitAt n xs = Stream.splitAt n (stream xs)-"splitAt -> unfused" [1] forall n xs.- Stream.splitAt n (stream xs) = splitAt n xs+--"splitAt -> unfused" [1] forall n xs.+-- Stream.splitAt n (stream xs) = splitAt n xs #-} -- | /O(n)/,/fusion/. 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the@@ -1350,8 +1339,8 @@ {-# RULES "takeWhile -> fusible" [~1] forall f xs. takeWhile f xs = unstream (Stream.takeWhile f (stream xs))-"takeWhile -> unfused" [1] forall f xs.- unstream (Stream.takeWhile f (stream xs)) = takeWhile f xs+--"takeWhile -> unfused" [1] forall f xs.+-- unstream (Stream.takeWhile f (stream xs)) = takeWhile f xs #-} -- | /O(n)/,/fusion/. 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@:@@ -1373,8 +1362,8 @@ {-# RULES "dropWhile -> fusible" [~1] forall f xs. dropWhile f xs = unstream (Stream.dropWhile f (stream xs))-"dropWhile -> unfused" [1] forall f xs.- unstream (Stream.dropWhile f (stream xs)) = dropWhile f xs+--"dropWhile -> unfused" [1] forall f xs.+-- unstream (Stream.dropWhile f (stream xs)) = dropWhile f xs #-} -- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where@@ -1474,8 +1463,8 @@ {-# RULES "isPrefixOf -> fusible" [~1] forall xs ys. isPrefixOf xs ys = Stream.isPrefixOf (stream xs) (stream ys)-"isPrefixOf -> unfused" [1] forall xs ys.- Stream.isPrefixOf (stream xs) (stream ys) = isPrefixOf xs ys+--"isPrefixOf -> unfused" [1] forall xs ys.+-- Stream.isPrefixOf (stream xs) (stream ys) = isPrefixOf xs ys #-} -- | The 'isSuffixOf' function takes two lists and returns 'True'@@ -1517,8 +1506,8 @@ {-# RULES "elem -> fusible" [~1] forall x xs. elem x xs = Stream.elem x (stream xs)-"elem -> unfused" [1] forall x xs.- Stream.elem x (stream xs) = elem x xs+--"elem -> unfused" [1] forall x xs.+-- Stream.elem x (stream xs) = elem x xs #-} -- | /O(n)/, /fusion/. 'notElem' is the negation of 'elem'.@@ -1550,8 +1539,8 @@ {-# RULES "lookup -> fusible" [~1] forall x xs. lookup x xs = Stream.lookup x (stream xs)-"lookup -> unfused" [1] forall x xs.- Stream.lookup x (stream xs) = lookup x xs+--"lookup -> unfused" [1] forall x xs.+-- Stream.lookup x (stream xs) = lookup x xs #-} -- | /O(n)/,/fusion/. 'filter', applied to a predicate and a list, returns the list of@@ -1576,8 +1565,8 @@ {-# RULES "filter -> fusible" [~1] forall f xs. filter f xs = unstream (Stream.filter f (stream xs))-"filter -> unfused" [1] forall f xs.- unstream (Stream.filter f (stream xs)) = filter f xs+--"filter -> unfused" [1] forall f xs.+-- unstream (Stream.filter f (stream xs)) = filter f xs #-} ------------------------------------------------------------------------@@ -1598,8 +1587,8 @@ {-# RULES "find -> fusible" [~1] forall f xs. find f xs = Stream.find f (stream xs)-"find -> unfused" [1] forall f xs.- Stream.find f (stream xs) = find f xs+--"find -> unfused" [1] forall f xs.+-- Stream.find f (stream xs) = find f xs #-} -- | The 'partition' function takes a predicate a list and returns@@ -1637,8 +1626,8 @@ {-# RULES "!! -> fusible" [~1] forall xs n. xs !! n = Stream.index (stream xs) n-"!! -> unfused" [1] forall xs n.- Stream.index (stream xs) n = xs !! n+-- "!! -> unfused" [1] forall xs n.+-- Stream.index (stream xs) n = xs !! n #-} -- | The 'elemIndex' function returns the index of the first element@@ -1725,8 +1714,8 @@ {-# RULES "findIndex -> fusible" [~1] forall f xs. findIndex f xs = Stream.findIndex f (stream xs)-"findIndex -> unfused" [1] forall f xs.- Stream.findIndex f (stream xs) = findIndex f xs+-- "findIndex -> unfused" [1] forall f xs.+-- Stream.findIndex f (stream xs) = findIndex f xs #-} -- | /O(n)/,/fusion/. The 'findIndices' function extends 'findIndex', by@@ -1749,8 +1738,8 @@ {-# RULES "findIndices -> fusible" [~1] forall p xs. findIndices p xs = unstream (Stream.findIndices p (stream xs))-"findIndices -> unfused" [1] forall p xs.- unstream (Stream.findIndices p (stream xs)) = findIndices p xs+-- "findIndices -> unfused" [1] forall p xs.+-- unstream (Stream.findIndices p (stream xs)) = findIndices p xs #-} ------------------------------------------------------------------------@@ -1772,8 +1761,8 @@ {-# RULES "zip -> fusible" [~1] forall xs ys. zip xs ys = unstream (Stream.zip (stream xs) (stream ys))-"zip -> unfused" [1] forall xs ys.- unstream (Stream.zip (stream xs) (stream ys)) = zip xs ys+-- "zip -> unfused" [1] forall xs ys.+-- unstream (Stream.zip (stream xs) (stream ys)) = zip xs ys #-} -- | /O(n)/,/fusion/. 'zip3' takes three lists and returns a list of@@ -1791,8 +1780,8 @@ {-# RULES "zip3 -> fusible" [~1] forall xs ys zs. zip3 xs ys zs = unstream (Stream.zipWith3 (,,) (stream xs) (stream ys) (stream zs))-"zip3 -> unfused" [1] forall xs ys zs.- unstream (Stream.zipWith3 (,,) (stream xs) (stream ys) (stream zs)) = zip3 xs ys zs+-- "zip3 -> unfused" [1] forall xs ys zs.+-- unstream (Stream.zipWith3 (,,) (stream xs) (stream ys) (stream zs)) = zip3 xs ys zs #-} -- | /O(n)/,/fusion/. The 'zip4' function takes four lists and returns a list of@@ -1835,8 +1824,8 @@ {-# RULES "zipWith -> fusible" [~1] forall f xs ys. zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))-"zipWith -> unfused" [1] forall f xs ys.- unstream (Stream.zipWith f (stream xs) (stream ys)) = zipWith f xs ys+-- "zipWith -> unfused" [1] forall f xs ys.+-- unstream (Stream.zipWith f (stream xs) (stream ys)) = zipWith f xs ys #-} -- | /O(n)/,/fusion/. The 'zipWith3' function takes a function which@@ -1855,8 +1844,8 @@ {-# RULES "zipWith3 -> fusible" [~1] forall f xs ys zs. zipWith3 f xs ys zs = unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs))-"zipWith3 -> unfused" [1] forall f xs ys zs.- unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs)) = zipWith3 f xs ys zs+-- "zipWith3 -> unfused" [1] forall f xs ys zs.+-- unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs)) = zipWith3 f xs ys zs #-} -- | /O(n)/,/fusion/. The 'zipWith4' function takes a function which combines four@@ -1871,8 +1860,8 @@ {-# RULES "zipWith4 -> fusible" [~1] forall f ws xs ys zs. zipWith4 f ws xs ys zs = unstream (Stream.zipWith4 f (stream ws) (stream xs) (stream ys) (stream zs))-"zipWith4 -> unfused" [1] forall f ws xs ys zs.- unstream (Stream.zipWith4 f (stream ws) (stream xs) (stream ys) (stream zs)) = zipWith4 f ws xs ys zs+-- "zipWith4 -> unfused" [1] forall f ws xs ys zs.+-- unstream (Stream.zipWith4 f (stream ws) (stream xs) (stream ys) (stream zs)) = zipWith4 f ws xs ys zs #-} -- | The 'zipWith5' function takes a function which combines five@@ -2280,8 +2269,8 @@ {-# RULES "insertBy -> fusible" [~1] forall f x xs. insertBy f x xs = unstream (Stream.insertBy f x (stream xs))-"insertBy -> unfused" [1] forall f x xs.- unstream (Stream.insertBy f x (stream xs)) = insertBy f x xs+-- "insertBy -> unfused" [1] forall f x xs.+-- unstream (Stream.insertBy f x (stream xs)) = insertBy f x xs #-} -- | /O(n)/,/fusion/. The 'maximumBy' function takes a comparison function and a list@@ -2300,8 +2289,8 @@ {-# RULES "maximumBy -> fused" [~1] forall p xs. maximumBy p xs = Stream.maximumBy p (stream xs)-"maximumBy -> unfused" [1] forall p xs.- Stream.maximumBy p (stream xs) = maximumBy p xs+-- "maximumBy -> unfused" [1] forall p xs.+-- Stream.maximumBy p (stream xs) = maximumBy p xs #-} -- | /O(n)/,/fusion/. The 'minimumBy' function takes a comparison function and a list@@ -2319,8 +2308,8 @@ {-# RULES "minimumBy -> fused" [~1] forall p xs. minimumBy p xs = Stream.minimumBy p (stream xs)-"minimumBy -> unfused" [1] forall p xs.- Stream.minimumBy p (stream xs) = minimumBy p xs+-- "minimumBy -> unfused" [1] forall p xs.+-- Stream.minimumBy p (stream xs) = minimumBy p xs #-} ------------------------------------------------------------------------@@ -2338,8 +2327,8 @@ {-# RULES "genericLength -> fusible" [~1] forall xs. genericLength xs = Stream.genericLength (stream xs)-"genericLength -> unfused" [1] forall xs.- Stream.genericLength (stream xs) = genericLength xs+-- "genericLength -> unfused" [1] forall xs.+-- Stream.genericLength (stream xs) = genericLength xs #-} {-# RULES@@ -2359,8 +2348,8 @@ {-# RULES "genericTake -> fusible" [~1] forall xs n. genericTake n xs = unstream (Stream.genericTake n (stream xs))-"genericTake -> unfused" [1] forall xs n.- unstream (Stream.genericTake n (stream xs)) = genericTake n xs+-- "genericTake -> unfused" [1] forall xs n.+-- unstream (Stream.genericTake n (stream xs)) = genericTake n xs #-} {-# RULES@@ -2379,8 +2368,8 @@ {-# RULES "genericDrop -> fusible" [~1] forall xs n. genericDrop n xs = unstream (Stream.genericDrop n (stream xs))-"genericDrop -> unfused" [1] forall xs n.- unstream (Stream.genericDrop n (stream xs)) = genericDrop n xs+-- "genericDrop -> unfused" [1] forall xs n.+-- unstream (Stream.genericDrop n (stream xs)) = genericDrop n xs #-} {-# RULES@@ -2405,8 +2394,8 @@ {-# RULES "genericIndex -> fusible" [~1] forall xs n. genericIndex xs n = Stream.genericIndex (stream xs) n-"genericIndex -> unfused" [1] forall xs n.- Stream.genericIndex (stream xs) n = genericIndex n xs+-- "genericIndex -> unfused" [1] forall xs n.+-- Stream.genericIndex (stream xs) n = genericIndex n xs #-} {-# RULES@@ -2427,8 +2416,8 @@ {-# RULES "genericSplitAt -> fusible" [~1] forall xs n. genericSplitAt n xs = Stream.genericSplitAt n (stream xs)-"genericSplitAt -> unfused" [1] forall xs n.- Stream.genericSplitAt n (stream xs) = genericSplitAt n xs+-- "genericSplitAt -> unfused" [1] forall xs n.+-- Stream.genericSplitAt n (stream xs) = genericSplitAt n xs #-} {-# RULES
Data/Stream.hs view
@@ -1,3 +1,4 @@+-- #hide {-# OPTIONS_GHC -fdicts-cheap -fbang-patterns #-} -- |@@ -12,24 +13,18 @@ -- -- Stream fusion for sequences. Described in: ----- * /Stream Fusion: From Lists to Streams to Nothing at All/, by--- Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007.--- <http://www.cse.unsw.edu.au/~dons/papers/CLS07.html>------ * /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and+-- /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and -- Roman Leshchinskiy, Practical Aspects of Declarative Languages -- 8th International Symposium, PADL 2007, 2007.--- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html> ----- See the source for the complete story:+-- /Stream Fusion: From Lists to Streams to Nothing at All/, by+-- Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007. ----- * <http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs>+-- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html>+-- <http://www.cse.unsw.edu.au/~dons/papers/CLS07.html> --- module Data.Stream ( -#ifndef __HADDOCK__- -- * The stream data type Stream(Stream), Step(..),@@ -230,12 +225,9 @@ bind, -- :: (a -> Bool) -> (a -> [b]) -> [a] -> [b] mapFilter, -- :: (a -> Bool) -> (a -> b) -> [a] -> [b] declare -- :: (a -> Stream b) -> a -> Stream b-#endif ) where -#ifndef __HADDOCK__- #ifndef EXTERNAL_PACKAGE import {-# SOURCE #-} GHC.Err (error)@@ -302,63 +294,61 @@ instance Functor Stream where fmap = map --- | A class of strict unlifted types. The Unlifted constraint in the--- Stream type above enforces a separation between user's types and the--- types used in stream states.+-- A class of strict unlifted types. The Unlifted constraint in the Stream+-- type above enforces a separation between user's types and the types used+-- in stream states. -- class Unlifted a where - -- | This expose function needs to be called in folds/loops that consume+ -- This expose function needs to be called in folds/loops that consume -- streams to expose the structure of the stream state to the simplifier -- In particular, to SpecConstr. -- expose :: a -> b -> b expose = seq - -- | This makes GHC's optimiser happier; it sometimes produces really bad+ -- This makes GHC's optimiser happier; it sometimes produces really bad -- code for single-method dictionaries -- unlifted_dummy :: a unlifted_dummy = error "unlifted_dummy" ----- | Unlifted versions of () and Bool for use in Stream states.+-- Unlifted versions of () and Bool for use in Stream states. -- data None = None instance Unlifted None --- | A useful unlifted type data Switch = S1 | S2 instance Unlifted Switch --- | Unlifted pairs, Maybe and Either+-- Unlifted pairs, Maybe and Either -- data (Unlifted a, Unlifted b) => a :!: b = !a :!: !b instance (Unlifted a, Unlifted b) => Unlifted (a :!: b) where expose (a :!: b) s = expose a (expose b s) {-# INLINE expose #-} --- | Unlifted Maybes data Unlifted a => Maybe a = Nothing | Just !a instance Unlifted a => Unlifted (Maybe a) where expose (Just a) s = expose a s expose Nothing s = s {-# INLINE expose #-} --- | Unlifted sums data (Unlifted a, Unlifted b) => Either a b = Left !a | Right !b instance (Unlifted a, Unlifted b) => Unlifted (Either a b) where expose (Left a) s = expose a s expose (Right b) s = expose b s {-# INLINE expose #-} --- | Some stream functions (notably concatMap) need to use a stream as a state+-- Some stream functions (notably concatMap) need to use a stream as a state -- instance Unlifted (Stream a) where expose (Stream next s0) s = seq next (seq s0 s) {-# INLINE expose #-} --- | Boxes for user's state. This is the gateway for user's types into unlifted++-- Boxes for user's state. This is the gateway for user's types into unlifted -- stream states. The L is always safe since it's lifted/lazy, exposing/seqing -- it does nothing. -- S is unlifted and so is only suitable for users states that we know we can@@ -1803,5 +1793,3 @@ moduleError :: String -> String -> a moduleError fun msg = error ("List." ++ fun ++ ':':' ':msg) {-# NOINLINE moduleError #-}--#endif
stream-fusion.cabal view
@@ -1,5 +1,5 @@ Name: stream-fusion-Version: 0.1.1+Version: 0.1.2 Author: Duncan Coutts, Don Stewart Maintainer: duncan.coutts@worc.ox.ac.uk, dons@galois.com License: BSD3@@ -15,6 +15,7 @@ To use, simply import Data.List.Stream in place of Data.List, and hide list functions from the Prelude. Category: Data+Build-Type: Simple Build-Depends: base Stability: experimental Tested-with: GHC==6.8@@ -22,4 +23,16 @@ Data.List.Stream Control.Monad.Stream Extensions: CPP, BangPatterns, ExistentialQuantification-ghc-options: -fglasgow-exts -O2 -Wall -fno-warn-orphans -DEXTERNAL_PACKAGE -fliberate-case-threshold100 -fdicts-cheap -fno-method-sharing+cpp-options: -DEXTERNAL_PACKAGE+ghc-options: -fglasgow-exts+ -O2+ -fvia-C -optc-O2+ -fspec-constr+ -funbox-strict-fields + -fdicts-cheap+ -fno-method-sharing+ -fmax-simplifier-iterations10+ -fliberate-case-threshold100+ -Wall+ -fno-warn-orphans+