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