git.iko.soy/streamly
on efe0be3 help sign in
streamly/core/src/Streamly/Internal/Data/List.hs
168 lines 5.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.Cross (CrossStream(..))
70import Streamly.Internal.Data.Stream.Type (Stream)
71import Streamly.Internal.Data.Stream.Zip (ZipStream(..))
72import Text.Read (readPrec)
74import qualified Streamly.Internal.Data.Stream.StreamK.Type as K
75import qualified Streamly.Internal.Data.Stream.Type as Stream
77-- XXX Rename to PureStream.
79-- | @List a@ is a replacement for @[a]@.
80--
81-- /Pre-release/
82newtype List a = List { toCrossStream :: CrossStream Identity a }
83 deriving
84 ( Eq, Ord
85 , Semigroup, Monoid, Functor, Foldable
86 , Applicative, Traversable, Monad, IsList)
88toStream :: List a -> Stream Identity a
89toStream = unCrossStream . toCrossStream
91fromStream :: Stream Identity a -> List a
92fromStream xs = List (CrossStream xs)
94instance (a ~ Char) => IsString (List a) where
95 {-# INLINE fromString #-}
96 fromString = List . fromList
98instance Show a => Show (List a) where
99 show (List x) = show $ unCrossStream x
101instance Read a => Read (List a) where
102 readPrec = fromStream <$> readPrec
104------------------------------------------------------------------------------
105-- Patterns
106------------------------------------------------------------------------------
108-- Note: When using the OverloadedLists extension we should be able to pattern
109-- match using the regular list contructors. OverloadedLists uses 'toList' to
110-- perform the pattern match, it should not be too bad as it works lazily in
111-- the Identity monad. We need these patterns only when not using that
112-- extension.
114-- | An empty list constructor and pattern that matches an empty 'List'.
115-- Corresponds to '[]' for Haskell lists.
116--
117pattern Nil :: List a
118pattern Nil <- (runIdentity . K.null . Stream.toStreamK . toStream -> True)
120 where
122 Nil = List $ CrossStream (Stream.fromStreamK K.nil)
124infixr 5 `Cons`
126-- | A list constructor and pattern that deconstructs a 'List' into its head
127-- and tail. Corresponds to ':' for Haskell lists.
128--
129pattern Cons :: a -> List a -> List a
130pattern Cons x xs <-
131 (fmap (second (List . CrossStream . Stream.fromStreamK))
132 . runIdentity . K.uncons . Stream.toStreamK . toStream
133 -> Just (x, xs)
134 )
136 where
138 Cons x xs = List $ CrossStream $ Stream.cons x (toStream xs)
140{-# COMPLETE Nil, Cons #-}
142------------------------------------------------------------------------------
143-- ZipList
144------------------------------------------------------------------------------
146-- | Just like 'List' except that it has a zipping 'Applicative' instance
147-- and no 'Monad' instance.
148--
149newtype ZipList a = ZipList { toZipStream :: ZipStream Identity a }
150 deriving
151 ( Show, Read, Eq, Ord
152 , Semigroup, Monoid, Functor, Foldable
153 , Applicative, Traversable, IsList
154 )
156instance (a ~ Char) => IsString (ZipList a) where
157 {-# INLINE fromString #-}
158 fromString = ZipList . fromList
160-- | Convert a 'ZipList' to a regular 'List'
161--
162fromZipList :: ZipList a -> List a
163fromZipList (ZipList zs) = List $ CrossStream (unZipStream zs)
165-- | Convert a regular 'List' to a 'ZipList'
166--
167toZipList :: List a -> ZipList a
168toZipList = ZipList . ZipStream . toStream