git.iko.soy/streamly
on cedc81c help sign in
streamly/core/src/Streamly/Internal/Data/List.hs
234 lines 7.5 kB history raw
1{-# LANGUAGE UndecidableInstances #-}
3-- |
4-- Module : Streamly.Internal.Data.List
5-- Copyright : (c) 2018 Composewell Technologies
6--
7-- License : BSD3
8-- Maintainer : streamly@composewell.com
9-- Portability : GHC
10--
11-- Lists are just a special case of monadic streams. The stream type @Stream
12-- Identity a@ can be used as a replacement for @[a]@. The 'List' type in this
13-- module is just a newtype wrapper around @Stream Identity@ for better type
14-- inference when using the 'OverloadedLists' GHC extension. @List a@ provides
15-- better performance compared to @[a]@. Standard list, string and list
16-- comprehension syntax can be used with the 'List' type by enabling
17-- 'OverloadedLists', 'OverloadedStrings' and 'MonadComprehensions' GHC
18-- extensions. There would be a slight difference in the 'Show' and 'Read'
19-- strings of streamly list as compared to regular lists.
20--
21-- Conversion to stream types is free, any stream combinator can be used on
22-- lists by converting them to streams. However, for convenience, this module
23-- provides combinators that work directly on the 'List' type.
24--
25--
26-- @
27-- List $ S.map (+ 1) $ toStream (1 \`Cons\` Nil)
28-- @
29--
30-- To convert a 'List' to regular lists, you can use any of the following:
31--
32-- * @toList . toStream@ and @toStream . fromList@
33-- * 'Data.Foldable.toList' from "Data.Foldable"
34-- * 'GHC.Exts.toList' and 'GHC.Exts.fromList' from 'IsList' in "GHC.Exts"
35--
36-- If you have made use of 'Nil' and 'Cons' constructors in the code and you
37-- want to replace streamly lists with standard lists, all you need to do is
38-- import these definitions:
39--
40-- @
41-- type List = []
42-- pattern Nil <- [] where Nil = []
43-- pattern Cons x xs = x : xs
44-- infixr 5 `Cons`
45-- {-\# COMPLETE Cons, Nil #-}
46-- @
47--
48-- See <src/docs/streamly-vs-lists.md> for more details and
49-- <src/test/PureStreams.hs> for comprehensive usage examples.
50--
51module Streamly.Internal.Data.List
52 (
53 List (Nil, Cons)
55 , toStream
56 , fromStream
58 -- XXX we may want to use rebindable syntax for variants instead of using
59 -- different types (applicative do and apWith).
60 , ZipList (..)
61 , fromZipList
62 , toZipList
63 )
64where
66import Control.Arrow (second)
67import Data.Functor.Identity (Identity, runIdentity)
68import GHC.Exts (IsList(..), IsString(..))
69import Streamly.Internal.Data.Stream.Type
70 ( CrossStream
71 , mkCross
72 , unCross
73 )
74import Streamly.Internal.Data.Stream.Type (Stream)
75import Text.Read
76 ( Lexeme(Ident), lexP, parens, prec, readPrec, readListPrec
77 , readListPrecDefault)
79import qualified Streamly.Internal.Data.StreamK.Type as K
80import qualified Streamly.Internal.Data.Stream.Type as Stream
81import qualified Streamly.Internal.Data.Stream.Generate as Stream
83-- XXX Rename to PureStream.
85-- | @List a@ is a replacement for @[a]@.
86--
87-- /Pre-release/
88newtype List a = List { toCrossStream :: CrossStream Identity a }
89 deriving
90 ( Eq, Ord
91 , Functor, Foldable
92 , Applicative, Monad, IsList)
94toStream :: List a -> Stream Identity a
95toStream = unCross . toCrossStream
97fromStream :: Stream Identity a -> List a
98fromStream xs = List (mkCross xs)
100instance (a ~ Char) => IsString (List a) where
101 {-# INLINE fromString #-}
102 fromString = List . fromList
104instance Show a => Show (List a) where
105 show (List x) = show $ unCross x
107instance Read a => Read (List a) where
108 readPrec = fromStream <$> readPrec
110------------------------------------------------------------------------------
111-- Patterns
112------------------------------------------------------------------------------
114-- Note: When using the OverloadedLists extension we should be able to pattern
115-- match using the regular list contructors. OverloadedLists uses 'toList' to
116-- perform the pattern match, it should not be too bad as it works lazily in
117-- the Identity monad. We need these patterns only when not using that
118-- extension.
120-- | An empty list constructor and pattern that matches an empty 'List'.
121-- Corresponds to '[]' for Haskell lists.
122--
123pattern Nil :: List a
124pattern Nil <- (runIdentity . K.null . Stream.toStreamK . toStream -> True)
126 where
128 Nil = List $ mkCross (Stream.fromStreamK K.nil)
130infixr 5 `Cons`
132-- | A list constructor and pattern that deconstructs a 'List' into its head
133-- and tail. Corresponds to ':' for Haskell lists.
134--
135pattern Cons :: a -> List a -> List a
136pattern Cons x xs <-
137 (fmap (second (List . mkCross . Stream.fromStreamK))
138 . runIdentity . K.uncons . Stream.toStreamK . toStream
139 -> Just (x, xs)
140 )
142 where
144 Cons x xs = List $ mkCross $ Stream.cons x (toStream xs)
146{-# COMPLETE Nil, Cons #-}
148------------------------------------------------------------------------------
149-- ZipStream
150------------------------------------------------------------------------------
152-- $setup
153-- >>> import qualified Streamly.Data.Fold as Fold
154-- >>> import qualified Streamly.Data.Stream as Stream
155-- >>> import qualified Streamly.Internal.Data.Stream.Zip as Stream
157------------------------------------------------------------------------------
158-- Serially Zipping Streams
159------------------------------------------------------------------------------
161-- | For 'ZipStream':
162--
163-- @
164-- (<>) = 'Streamly.Data.Stream.append'
165-- (\<*>) = 'Streamly.Data.Stream.zipWith' id
166-- @
167--
168-- Applicative evaluates the streams being zipped serially:
169--
170-- >>> s1 = Stream.ZipStream $ Stream.fromFoldable [1, 2]
171-- >>> s2 = Stream.ZipStream $ Stream.fromFoldable [3, 4]
172-- >>> s3 = Stream.ZipStream $ Stream.fromFoldable [5, 6]
173-- >>> s = (,,) <$> s1 <*> s2 <*> s3
174-- >>> Stream.fold Fold.toList (Stream.unZipStream s)
175-- [(1,3,5),(2,4,6)]
176--
177newtype ZipStream m a = ZipStream {unZipStream :: Stream m a}
178 deriving (Functor)
180deriving instance IsList (ZipStream Identity a)
181deriving instance (a ~ Char) => IsString (ZipStream Identity a)
182deriving instance Eq a => Eq (ZipStream Identity a)
183deriving instance Ord a => Ord (ZipStream Identity a)
184deriving instance (Foldable m, Monad m) => Foldable (ZipStream m)
186instance Show a => Show (ZipStream Identity a) where
187 showsPrec p dl = showParen (p > 10) $
188 showString "fromList " . shows (toList dl)
190instance Read a => Read (ZipStream Identity a) where
191 readPrec = parens $ prec 10 $ do
192 Ident "fromList" <- lexP
193 fromList <$> readPrec
194 readListPrec = readListPrecDefault
196type ZipSerialM = ZipStream
198-- | An IO stream whose applicative instance zips streams serially.
199--
200type ZipSerial = ZipSerialM IO
202instance Monad m => Applicative (ZipStream m) where
203 pure = ZipStream . Stream.repeat
205 {-# INLINE (<*>) #-}
206 ZipStream m1 <*> ZipStream m2 = ZipStream $ Stream.zipWith id m1 m2
208------------------------------------------------------------------------------
209-- ZipList
210------------------------------------------------------------------------------
212-- | Just like 'List' except that it has a zipping 'Applicative' instance
213-- and no 'Monad' instance.
214--
215newtype ZipList a = ZipList { toZipStream :: ZipStream Identity a }
216 deriving
217 ( Show, Read, Eq, Ord
218 , Functor, Foldable
219 , Applicative, IsList
220 )
222instance (a ~ Char) => IsString (ZipList a) where
223 {-# INLINE fromString #-}
224 fromString = ZipList . fromList
226-- | Convert a 'ZipList' to a regular 'List'
227--
228fromZipList :: ZipList a -> List a
229fromZipList (ZipList zs) = List $ mkCross (unZipStream zs)
231-- | Convert a regular 'List' to a 'ZipList'
232--
233toZipList :: List a -> ZipList a
234toZipList = ZipList . ZipStream . toStream