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