git.iko.soy/streamly
on d1146fb help sign in
streamly/src/Streamly/Internal/Data/List.hs
193 lines 6.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-- Stability : pre-release
10-- Portability : GHC
11--
12-- Lists are just a special case of monadic streams. The stream type @SerialT
13-- Identity a@ can be used as a replacement for @[a]@. The 'List' type in this
14-- module is just a newtype wrapper around @SerialT Identity@ for better type
15-- inference when using the 'OverloadedLists' GHC extension. @List a@ provides
16-- better performance compared to @[a]@. Standard list, string and list
17-- comprehension syntax can be used with the 'List' type by enabling
18-- 'OverloadedLists', 'OverloadedStrings' and 'MonadComprehensions' GHC
19-- extensions. There would be a slight difference in the 'Show' and 'Read'
20-- strings of streamly list as compared to regular lists.
21--
22-- Conversion to stream types is free, any stream combinator can be used on
23-- lists by converting them to streams. However, for convenience, this module
24-- provides combinators that work directly on the 'List' type.
25--
26--
27-- @
28-- List $ S.map (+ 1) $ toSerial (1 \`Cons\` Nil)
29-- @
30--
31-- To convert a 'List' to regular lists, you can use any of the following:
32--
33-- * @toList . toSerial@ and @toSerial . fromList@
34-- * 'Data.Foldable.toList' from "Data.Foldable"
35-- * 'GHC.Exts.toList' and 'GHC.Exts.fromList' from 'IsList' in "GHC.Exts"
36--
37-- If you have made use of 'Nil' and 'Cons' constructors in the code and you
38-- want to replace streamly lists with standard lists, all you need to do is
39-- import these definitions:
40--
41-- @
42-- type List = []
43-- pattern Nil <- [] where Nil = []
44-- pattern Cons x xs = x : xs
45-- infixr 5 `Cons`
46-- {-\# COMPLETE Cons, Nil #-}
47-- @
48--
49-- See <src/docs/streamly-vs-lists.md> for more details and
50-- <src/test/PureStreams.hs> for comprehensive usage examples.
51--
52module Streamly.Internal.Data.List
53 (
54 List (.., Nil, Cons)
56 -- XXX we may want to use rebindable syntax for variants instead of using
57 -- different types (applicative do and apWith).
58 , ZipList (..)
59 , fromZipList
60 , toZipList
61 )
62where
64import Control.Arrow (second)
65import Control.DeepSeq (NFData(..))
66#if MIN_VERSION_deepseq(1,4,3)
67import Control.DeepSeq (NFData1(..))
68#endif
69import Data.Functor.Identity (Identity, runIdentity)
70#if __GLASGOW_HASKELL__ < 808
71import Data.Semigroup (Semigroup(..))
72#endif
73import GHC.Exts (IsList(..), IsString(..))
75import Streamly.Internal.Data.Stream.Serial (SerialT(..))
76import Streamly.Internal.Data.Stream.Zip (ZipSerialM(..))
78import qualified Streamly.Internal.Data.Stream.Serial as Serial
79import qualified Streamly.Internal.Data.Stream.StreamK.Type as K
81-- We implement list as a newtype instead of a type synonym to make type
82-- inference easier when using -XOverloadedLists and -XOverloadedStrings. When
83-- using a stream type the programmer needs to specify the Monad otherwise the
84-- type remains ambiguous.
85--
86-- XXX once we separate consM from IsStream or remove the MonadIO and
87-- MonadBaseControlIO dependency from it, then we can make this an instance of
88-- IsStream and use the regular polymorphic functions on Lists as well. Once
89-- that happens we can change the Show and Read instances as well to use "1 >:
90-- 2 >: nil" etc. or should we use a separate constructor indicating the "List"
91-- type ":>" for better inference?
92--
93-- | @List a@ is a replacement for @[a]@.
94--
95-- @since 0.6.0
96newtype List a = List { toSerial :: SerialT Identity a }
97 deriving (Show, Read, Eq, Ord, NFData
98#if MIN_VERSION_deepseq(1,4,3)
99 , NFData1
100#endif
101 , Semigroup, Monoid, Functor, Foldable
102 , Applicative, Traversable, Monad)
104instance (a ~ Char) => IsString (List a) where
105 {-# INLINE fromString #-}
106 fromString = List . fromList
108-- GHC versions 8.0 and below cannot derive IsList
109instance IsList (List a) where
110 type (Item (List a)) = a
111 {-# INLINE fromList #-}
112 fromList = List . fromList
113 {-# INLINE toList #-}
114 toList = toList . toSerial
116------------------------------------------------------------------------------
117-- Patterns
118------------------------------------------------------------------------------
120-- Note: When using the OverloadedLists extension we should be able to pattern
121-- match using the regular list contructors. OverloadedLists uses 'toList' to
122-- perform the pattern match, it should not be too bad as it works lazily in
123-- the Identity monad. We need these patterns only when not using that
124-- extension.
125--
126-- | An empty list constructor and pattern that matches an empty 'List'.
127-- Corresponds to '[]' for Haskell lists.
128--
129-- @since 0.6.0
130pattern Nil :: List a
131pattern Nil <- (runIdentity . K.null . getSerialT . toSerial -> True) where
132 Nil = List $ SerialT K.nil
134infixr 5 `Cons`
136-- | A list constructor and pattern that deconstructs a 'List' into its head
137-- and tail. Corresponds to ':' for Haskell lists.
138--
139-- @since 0.6.0
140pattern Cons :: a -> List a -> List a
141pattern Cons x xs <-
142 (fmap (second (List . SerialT))
143 . runIdentity . K.uncons . getSerialT . toSerial
144 -> Just (x, xs)
145 )
147 where
149 Cons x xs = List $ Serial.cons x (toSerial xs)
151#if __GLASGOW_HASKELL__ >= 802
152{-# COMPLETE Nil, Cons #-}
153#endif
155------------------------------------------------------------------------------
156-- ZipList
157------------------------------------------------------------------------------
159-- | Just like 'List' except that it has a zipping 'Applicative' instance
160-- and no 'Monad' instance.
161--
162-- @since 0.6.0
163newtype ZipList a = ZipList { toZipSerial :: ZipSerialM Identity a }
164 deriving (Show, Read, Eq, Ord, NFData
165#if MIN_VERSION_deepseq(1,4,3)
166 , NFData1
167#endif
168 , Semigroup, Monoid, Functor, Foldable
169 , Applicative, Traversable)
171instance (a ~ Char) => IsString (ZipList a) where
172 {-# INLINE fromString #-}
173 fromString = ZipList . fromList
175-- GHC versions 8.0 and below cannot derive IsList
176instance IsList (ZipList a) where
177 type (Item (ZipList a)) = a
178 {-# INLINE fromList #-}
179 fromList = ZipList . fromList
180 {-# INLINE toList #-}
181 toList = toList . toZipSerial
183-- | Convert a 'ZipList' to a regular 'List'
184--
185-- @since 0.6.0
186fromZipList :: ZipList a -> List a
187fromZipList (ZipList zs) = List $ SerialT $ getZipSerialM zs
189-- | Convert a regular 'List' to a 'ZipList'
190--
191-- @since 0.6.0
192toZipList :: List a -> ZipList a
193toZipList = ZipList . ZipSerialM . getSerialT . toSerial