stream-fusion 0.1.2 → 0.1.2.1
raw patch · 5 files changed
+53/−25 lines, 5 files
Files
- Data/List/Stream.hs +16/−5
- Data/Stream.hs +28/−16
- stream-fusion.cabal +2/−2
- tests/Bench/StreamList.hs +6/−1
- tests/Examples/SumReplicate.hs +1/−1
Data/List/Stream.hs view
@@ -10,14 +10,21 @@ -- -- A reimplementation of the standard Haskell list library to take advantage of -- stream fusion, and new GHC optimisations. The fusion mechanism is--- based on that described in:+-- based on stream fusion for sequences. Described in: ----- /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and+-- * /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 -- 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>+-- -- This library is a drop in replacement for "Data.List". -- module Data.List.Stream (@@ -629,9 +636,11 @@ -- | /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@@ -662,9 +671,11 @@ 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@@ -935,7 +946,7 @@ {-# RULES "strictMaximum -> fused" [~1] forall xs.- maximum xs = Stream.strictMaximum (stream xs)+ strictMaximum xs = Stream.strictMaximum (stream xs) --"strictMaximum -> unfused" [1] forall xs. -- Stream.strictMaximum (stream xs) = strictMaximum xs #-}@@ -968,7 +979,7 @@ {-# RULES "strictMinimum -> fused" [~1] forall xs.- maximum xs = Stream.strictMinimum (stream xs)+ strictMinimum xs = Stream.strictMinimum (stream xs) --"strictMinimum -> unfused" [1] forall xs. -- Stream.strictMinimum (stream xs) = strictMinimum xs #-}
Data/Stream.hs view
@@ -1,4 +1,3 @@--- #hide {-# OPTIONS_GHC -fdicts-cheap -fbang-patterns #-} -- |@@ -13,18 +12,24 @@ -- -- Stream fusion for sequences. Described in: ----- /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and+-- * /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 -- Roman Leshchinskiy, Practical Aspects of Declarative Languages -- 8th International Symposium, PADL 2007, 2007.+-- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html> ----- /Stream Fusion: From Lists to Streams to Nothing at All/, by--- Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007.+-- See the source for the complete story: ----- <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html>--- <http://www.cse.unsw.edu.au/~dons/papers/CLS07.html>+-- * <http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs> --+ module Data.Stream ( +#ifndef __HADDOCK__+ -- * The stream data type Stream(Stream), Step(..),@@ -225,9 +230,12 @@ 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)@@ -294,61 +302,63 @@ 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@@ -1793,3 +1803,5 @@ 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.2+Version: 0.1.2.1 Author: Duncan Coutts, Don Stewart Maintainer: duncan.coutts@worc.ox.ac.uk, dons@galois.com License: BSD3@@ -10,7 +10,7 @@ This package provides the standard Haskell list library reimplemented to allow stream fusion. This should in general provide faster list operations, and faster code for list-heavy- programs. See the paper "Stream Fusion: From Lists to Streams to Nothing at All",+ programs. See the paper /Stream Fusion: From Lists to Streams to Nothing at All/, Coutts, Leshchinskiy and Stewart, 2007. To use, simply import Data.List.Stream in place of Data.List, and hide list functions from the Prelude.
tests/Bench/StreamList.hs view
@@ -148,8 +148,10 @@ -- * Special lists -- ** Functions on strings+{- unlines :: [String] -> String lines :: String -> [String]+-} {- words :: String -> [String] unwords :: [String] -> String@@ -225,7 +227,8 @@ -- ** Special folds concat = \ xs -> Stream.concat (s xs)-concatMap = \f xs -> Stream.concatMap f (s xs)+ -- concatMap :: (a -> Stream b) -> Stream a -> Stream b+concatMap = \f xs -> u $ Stream.concatMap (s . f) (s xs) and = \ xs -> Stream.and (s xs) or = \ xs -> Stream.or (s xs) any = \f xs -> Stream.any f (s xs)@@ -343,8 +346,10 @@ -- * Special lists -- ** Functions on strings+{- unlines = \xs -> Stream.concatMap (\x -> x ++ ['\n']) (s xs) lines = \xs -> u (Stream.lines (s xs))+-} {- words = Stream.words
tests/Examples/SumReplicate.hs view
@@ -1,6 +1,6 @@ module FuseTest where -import Data.List.Stream as L+import Data.List as L foo :: Int -> Int foo n = L.sum (L.replicate n 1)