list-transformer 1.0.4 → 1.1.1
raw patch · 4 files changed
Files
- CHANGELOG.md +50/−0
- LICENSE +2/−2
- list-transformer.cabal +12/−7
- src/List/Transformer.hs +406/−133
+ CHANGELOG.md view
@@ -0,0 +1,50 @@+1.1.1++- Support older versions of `base`++1.1.0:++- BREAKING CHANGE: Remove `MonadTrans` instance for `ZipListT`++1.0.9:++- `MFunctor` instances for `ListT` / `Step`++1.0.8:++- Improve documentation++1.0.7:++- Add `ZipListT`+- Add `dropWhile`++1.0.6:++- Build against GHC 8.8++1.0.5:++- Disable `-Wcompat` build flag for GHC < 8.0++1.0.4:++- Add `Semigroup` instance+- Make package `-Wcompat`-clean++1.0.3:++- Fix typos in tutorial++1.0.2:++- Add `takeWhile`+- Add `MonadFail` instance for `ListT`++1.0.1:++- Add `take` / `drop` / `unfold` / `zip`++1.0.0:++- Initial release
LICENSE view
@@ -1,4 +1,4 @@-Copyright Gabriel Gonzalez (c) 2016+Copyright Gabriella Gonzalez (c) 2016 All rights reserved. @@ -13,7 +13,7 @@ disclaimer in the documentation and/or other materials provided with the distribution. - * Neither the name of Gabriel Gonzalez nor the names of other+ * Neither the name of Gabriella Gonzalez nor the names of other contributors may be used to endorse or promote products derived from this software without specific prior written permission.
list-transformer.cabal view
@@ -1,5 +1,5 @@ name: list-transformer-version: 1.0.4+version: 1.1.1 synopsis: List monad transformer description: This library provides a list monad transformer that enriches lists with effects and streams efficiently in@@ -8,25 +8,30 @@ This library also has an extensive tutorial in the "List.Transformer" module which explains the motivation behind this type and how to use the type fluently.-homepage: https://github.com/Gabriel439/Haskell-List-Transformer-Library+homepage: https://github.com/Gabriella439/Haskell-List-Transformer-Library license: BSD3 license-file: LICENSE-author: Gabriel Gonzalez-maintainer: Gabriel439@gmail.com-copyright: 2016 Gabriel Gonzalez+author: Gabriella Gonzalez+maintainer: GenuineGabriella@gmail.com+copyright: 2016 Gabriella Gonzalez category: Control build-type: Simple cabal-version: >=1.10+extra-source-files: CHANGELOG.md library hs-source-dirs: src exposed-modules: List.Transformer default-language: Haskell2010 build-depends: base >= 4.5 && < 5- , mtl >= 2.1 && < 2.3+ , mtl >= 2.1 && < 2.4+ , mmorph >= 1.1.3 && < 1.3 if !impl(ghc >= 8.0) build-depends: semigroups == 0.18.*- ghc-options: -Wall -Wcompat+ if !impl(ghc >= 8.0)+ ghc-options: -Wall+ if impl(ghc >= 8.0)+ ghc-options: -Wall -Wcompat test-suite doctest type: exitcode-stdio-1.0
src/List/Transformer.hs view
@@ -1,24 +1,119 @@-{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE CPP #-}-{-# LANGUAGE DeriveFoldable #-}-{-# LANGUAGE DeriveTraversable #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveFoldable #-}+{-# LANGUAGE DeriveTraversable #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-} -{-| The `ListT` type is like a list that lets you interleave effects between- each element of the list. The type's definition is very short:+-- | The `ListT` type is like a list that lets you interleave effects between+-- each element of the list.+module List.Transformer+ (+ -- * Introduction+ -- $intro -> -- Every `ListT` begins with an outermost effect (the `m`)-> newtype ListT m a = ListT { next :: m (Step m a) }->->-> -- The return value of that effect is either-> -- * Cons: a new list element followed by the rest of the list-> -- * Nil : an empty list-> data Step m a = Cons a (ListT m a) | Nil+ -- ** Example: stdin, stdout+ -- $standardStreams - You most commonly use this type when you wish to generate each element of+ -- ** Core operations+ -- $core++ -- ** Monadic combination+ -- $monad++ -- ** Exercise: Interaction+ -- $interaction++ -- * ListT+ ListT(..)++ -- ** Consuming+ -- $pleaseStream+ , runListT+ , fold+ , foldM++ -- ** Constructing+ -- $constructing+ , select+ , unfold++ -- ** Removing elements+ , take+ , drop+ , dropWhile+ , takeWhile+ -- $filter++ -- ** Concatenation+ -- $concatenation++ -- ** Pairwise combination+ -- $pairwise+ , zip++ -- ** Repetition+ -- $repetition++ -- * Step+ , Step(..)++ -- * Alternative instances+ , ZipListT(..)++ -- * Re-exports+ , MonadTrans(..)+ , MonadIO(..)+ , Alternative(..)+ , MFunctor (..)+ ) where++#if MIN_VERSION_base(4,8,0)+import Control.Applicative (Alternative(..), liftA2)+#else+import Control.Applicative (Applicative(..), Alternative(..), liftA2)+import Data.Foldable (Foldable)+import Data.Functor ((<$))+import Data.Monoid (Monoid(..))+import Data.Traversable (Traversable)+#endif+import Control.Monad (MonadPlus(..))+import Control.Monad.Error.Class (MonadError(..))+#if MIN_VERSION_base(4,9,0) && !(MIN_VERSION_base(4,13,0))+import Control.Monad.Fail (MonadFail(..))+#endif+import Control.Monad.Morph (MFunctor (..))+import Control.Monad.State.Class (MonadState(..))+import Control.Monad.Reader.Class (MonadReader(..))+import Control.Monad.Trans (MonadTrans(..), MonadIO(..))+import Data.Semigroup (Semigroup(..))+import Prelude hiding (drop, dropWhile, pred, take, takeWhile, zip)++import qualified Data.Foldable++-- $setup+-- >>> :set -XNoMonomorphismRestriction++{- $intro++The type's definition is very short:++@newtype 'ListT' m a = ListT { next :: m ('Step' m a) }@++ Every `ListT` begins with an outermost effect (the @\'m\'@, commonly 'IO'). The return value of that effect is either:++@data 'Step' m a = Cons a ('ListT' m a) | Nil@++ * Cons: a new list element followed by the rest of the list+ * Nil : an empty list++-}++{- $standardStreams++ You most commonly use the ListT when you wish to generate each element of the list using `IO`. For example, you can read lines from standard input: > import List.Transformer@@ -65,21 +160,9 @@ > <Ctrl-D> > $ - Sometimes we can simplify the code by taking advantage of the fact that the- `Monad` instance for `ListT` behaves like a list comprehension:--> stdout :: ListT IO String -> IO ()-> stdout strings = runListT (do-> string <- strings-> liftIO (putStrLn string) )-- You can read the above code as saying: \"for each @string@ in @strings@,- call `putStrLn` on @string@.-- You can even use list comprehension syntax if you enable the- @MonadComprehensions@ language extension:+-} -> stdout strings = runListT [ r | str <- strings, r <- liftIO (putStrLn str) ]+{- $core The most important operations that you should familiarize yourself with are: @@ -99,130 +182,78 @@ > (<|>) :: ListT IO a -> ListT IO a -> ListT IO a - * (`>>=`), which powers @do@ notation and @MonadComprehensions@:+ * (`>>=`), which powers @do@ notation and @MonadComprehensions@ > (>>=) :: ListT IO a -> (a -> ListT IO b) -> ListT IO b - For example, suppose you want to build a `ListT` with three elements and- no effects. You could just write:+ * `select`, which converts a plain list into a `ListT` -> pure 1 <|> pure 2 <|> pure 3 :: ListT IO Int+> select :: [a] -> ListT IO a - ... although you would probably prefer to use `select` instead:+-} -> select :: [a] -> ListT IO a->-> select [1, 2, 3] :: ListT IO Int+{- $monad - To test your understanding, guess what this code does and then test your- guess by running the code:+ Sometimes we can simplify the code by taking advantage of the fact that the+ `Monad` instance for `ListT` behaves like a list comprehension: -> import List.Transformer->-> strings :: ListT IO String-> strings = do-> _ <- select (repeat ())-> liftIO (putStrLn "Say something:")-> liftIO getLine->-> main :: IO ()-> main = runListT (do-> string <- pure "Hello, there!" <|> strings+> stdout :: ListT IO String -> IO ()+> stdout strings = runListT (do+> string <- strings > liftIO (putStrLn string) ) - This library does not provide utilities like `mapM` because there are many- possible minor variations on `mapM` that we could write, such as:--> mapM :: Monad m => (a -> m b) -> [a] -> ListT m b-> mapM f xs = do-> x <- select xs-> lift (f x)->-> -- Alternatively, using MonadComprehensions:-> mapM f xs = [ r | x <- select xs, r <- lift (f x) ]+ You can read the above code as saying: \"for each @string@ in @strings@,+ call `putStrLn` on @string@." - ... or:+ You can even use list comprehension syntax if you enable the+ @MonadComprehensions@ language extension: -> mapM :: Monad m => (a -> m b) -> ListT m a -> ListT m b-> mapM f xs = do-> x <- xs-> lift (f x)->-> -- Alternatively, using MonadComprehensions:-> mapM f xs = [ r | x <- xs, r <- lift (f x) ]+> stdout strings = runListT [ r | str <- strings, r <- liftIO (putStrLn str) ] - ... or:+ There are a few ways we could consider defining a `ListT` analogue to the `mapM`+ function from `Prelude`, but none are given in this library because they need+ require only (`>>=`) and some trivial lifting. -> mapM :: Monad m => (a -> ListT m b) -> ListT m a -> ListT m b-> mapM f xs = do-> x <- xs-> f x->-> -- Alternatively, using MonadComprehensions:-> mapM f xs = [ r | x <- xs, r <- f x ]->-> -- Alternatively, using a pre-existing operator from "Control.Monad"-> mapM = (=<<)+> mapM :: (a -> IO b) -> [a] -> IO [b]+> ( \f xs -> xs >>= f ) :: (a -> ListT IO b) -> ListT IO a -> ListT IO b+> ( \f xs -> select xs >>= lift . f ) :: (a -> IO b) -> [a] -> ListT IO b+> ( \f xs -> xs >>= lift . f ) :: (a -> IO b) -> ListT IO a -> ListT IO b - Whichever one you prefer, all three variations still stream in constant- space (unlike @"Control.Monad".`mapM`@, which buffers the entire output- list before returning a single element).+ A critical difference between `mapM` and `ListT`'s monad is that `ListT` will+ stream in constant space, whereas `mapM` buffers the entire output list before+ returning a single element. - This library is designed to stream results in constant space and does not- expose an obvious way to collect all the results into memory. As a rule of- thumb if you think you need to collect all the results in memory try to- instead see if you can consume the results as they are being generated (such- as in all the above examples). If you can stream the data from start to- finish then your code will use significantly less memory and your program- will become more responsive. -}-module List.Transformer- ( -- * ListT- ListT(..)- , runListT- , fold- , foldM- , select- , take- , drop- , takeWhile- , unfold- , zip - -- * Step- , Step(..)+{- $interaction - -- * Re-exports- , MonadTrans(..)- , MonadIO(..)- , Alternative(..)- ) where+ To test your understanding, guess what this code does and then test your+ guess by running the code: -#if MIN_VERSION_base(4,8,0)-import Control.Applicative (Alternative(..), liftA2)-#else-import Control.Applicative (Applicative(..), Alternative(..), liftA2)-import Data.Foldable (Foldable)-import Data.Functor ((<$))-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable)-#endif-import Control.Monad (MonadPlus(..))-import Control.Monad.Error.Class (MonadError(..))-#if MIN_VERSION_base(4,9,0)-import Control.Monad.Fail (MonadFail(..))-#endif-import Control.Monad.State.Class (MonadState(..))-import Control.Monad.Reader.Class (MonadReader(..))-import Control.Monad.Trans (MonadTrans(..), MonadIO(..))-import Data.Semigroup (Semigroup(..))-import Prelude hiding (drop, pred, take, takeWhile, zip)+@+import List.Transformer ('ListT', 'runListT', 'liftIO', ('<|>'), 'select')+import Data.Foldable ('Data.Foldable.asum')+import Data.List ('Data.List.repeat') -import qualified Data.Foldable+strings :: 'ListT' IO String+strings = do+ 'select' ('Data.List.repeat' ())+ 'Data.Foldable.asum'+ [ pure ""+ , pure "Say something:"+ , do+ x <- 'liftIO' getLine+ return ("You said: " '<|>' x)+ ] --- $setup--- >>> :set -XNoMonomorphismRestriction+main :: IO ()+main = 'runListT' (do+ string \<- pure "Hello, there!" '<|>' strings+ 'liftIO' (putStrLn string) )+@ +-}+ {-| This is like a list except that you can interleave effects between each list element. For example: @@ -282,7 +313,9 @@ Nil -> return Nil Cons x l' -> next (k x <|> (l' >>= k)) ) +#if !(MIN_VERSION_base(4,13,0)) fail _ = mzero+#endif instance Monad m => Alternative (ListT m) where empty = ListT (return Nil)@@ -339,6 +372,13 @@ state k = lift (state k) +instance MFunctor ListT where+#if MIN_VERSION_base(4,8,0)+ hoist f xs = ListT (f (fmap (hoist f) (next xs)))+#else+ hoist f xs = ListT (f (next xs >>= \x -> return (hoist f x)))+#endif+ instance (Monad m, Num a) => Num (ListT m a) where fromInteger n = pure (fromInteger n) @@ -409,6 +449,9 @@ ... but you can also use the `fold` function directly: > fold (+) 0 id :: Num a => ListT m a -> m a++>>> fold (<>) "" id (select ["a", "b", "c", "d", "e"])+"abcde" -} fold :: Monad m => (x -> a -> x) -> x -> (x -> b) -> ListT m a -> m b fold step begin done l = go begin l@@ -442,6 +485,36 @@ go x' l' Nil -> done x +{- $pleaseStream++ This library is designed to stream results in constant space and does not+ expose an obvious way to collect all the results into memory. As a rule of+ thumb if you think you need to collect all the results in memory try to+ instead see if you can consume the results as they are being generated (such+ as in all the above examples). If you can stream the data from start to+ finish then your code will use significantly less memory and your program+ will become more responsive.++-}++{- $constructing++ `empty` is the empty list with no effects.++ Use `pure`/`return` to construct a singleton list with no effects. Use `liftIO`+ to turn an effect into a singleton list whose sole element is the effect's result.++ Suppose you want to build a `ListT` with three elements and no effects.+ You could write:++> pure 1 <|> pure 2 <|> pure 3 :: ListT IO Int++ ... although you would probably prefer to use `select` instead:++> select [1, 2, 3] :: ListT IO Int++-}+ {-| Convert any collection that implements `Foldable` to another collection that implements `Alternative` @@ -493,6 +566,27 @@ Cons _ l' -> next (drop (n-1) l') Nil -> return Nil) +-- | @dropWhile pred xs@ drops elements from the head of @xs@ if they+-- satisfy the predicate, but still runs their effects.+--+-- >>> let list xs = do x <- select xs; liftIO (print (show x)); return x+-- >>> let sum = fold (+) 0 id+-- >>> sum (dropWhile even (list [2,4,5,7,8]))+-- "2"+-- "4"+-- "5"+-- "7"+-- "8"+-- 20+dropWhile :: Monad m => (a -> Bool) -> ListT m a -> ListT m a+dropWhile pred l = ListT (do+ n <- next l+ case n of+ Cons x l'+ | pred x -> next (dropWhile pred l')+ | otherwise -> return (Cons x l')+ Nil -> return Nil )+ -- | @takeWhile pred xs@ takes elements from @xs@ until the predicate @pred@ fails -- -- >>> let list xs = do x <- select xs; liftIO (print (show x)); return x@@ -509,6 +603,135 @@ Cons x l' | pred x -> return (Cons x (takeWhile pred l')) _ -> return Nil ) +{- $filter++To filter elements from a list based on a predicate, use `Control.Monad.guard`.+For example, the following function is analogous to `Data.List.filter`:++> filter :: Monad m => (a -> m Bool) -> ListT m a -> ListT m a+> filter pred as = do+> a <- as+> b <- lift (pred a)+> guard b+> return a++-}++{- $concatenation++ Use (`<|>`) to concatenate two lists.++ > (<|>) :: ListT IO a -> ListT IO a -> ListT IO a++ Use `Data.Foldable.asum` to flatten a list of lists.++ > asum :: [ListT IO a] -> ListT IO a++ Use `Control.Monad.join` to flatten a `ListT` of `ListT`s.++ > join :: ListT IO (ListT IO a) -> ListT IO a++-}++{- $pairwise++ The (`<>`) operation joins every combination of an element from one list with+ an element from the other.++>>> runListT ( (select ["a", "b"] <> select ["1", "2", "3"]) >>= (liftIO . print) )+"a1"+"a2"+"a3"+"b1"+"b2"+"b3"++ This is the same combinatorial effect that (`>>=`) produces.++>>> runListT (do x <- select ["a", "b"]; y <- select ["1", "2", "3"]; liftIO (print (x <> y)))+"a1"+"a2"+"a3"+"b1"+"b2"+"b3"++-}++{- $repetition++Unbounded repetition can be induced using @'select' ('Data.List.repeat' ())@.+For example, here are several functions analogous to 'Data.List.cycle':++> cycle1 :: Monad m => a -> ListT m a+> cycle1 a = do+> select (Data.List.repeat ())+> return a++> cycle2 :: Monad m => [a] -> ListT m a+> cycle2 as = do+> select (Data.List.repeat ())+> select as++> cycle3 :: Monad m => m a -> ListT m a+> cycle3 m = do+> select (Data.List.repeat ())+> lift m++> cycle4 :: Monad m => [m a] -> ListT m a+> cycle4 ms = do+> select (Data.List.repeat ())+> m <- select ms+> lift m++> cycle5 :: Monad m => ListT m a -> ListT m a+> cycle5 x = do+> select (Data.List.repeat ())+> x++> cycle6 :: Monad m => [ListT m a] -> ListT m a+> cycle6 lists = do+> select (Data.List.repeat ())+> x <- select lists+> x++In a similar manner, we can use 'Data.List.replicate' as the initial selection+to achieve bounded repetition:++> replicate1 :: Monad m => Int -> a -> ListT m a+> replicate1 n a = do+> select (Data.List.replicate n ())+> return a++> replicate2 :: Monad m => Int -> [a] -> ListT m a+> replicate2 n as = do+> select (Data.List.replicate n ())+> select as++> replicate3 :: Monad m => Int -> m a -> ListT m a+> replicate3 n m = do+> select (Data.List.replicate n ())+> lift m++> replicate4 :: Monad m => Int -> [m a] -> ListT m a+> replicate4 n ms = do+> select (Data.List.replicate n ())+> m <- select ms+> lift m++> replicate5 :: Monad m => Int -> ListT m a -> ListT m a+> replicate5 n x = do+> select (Data.List.replicate n ())+> x++> replicate6 :: Monad m => Int -> [ListT m a] -> ListT m a+> replicate6 n lists = do+> select (Data.List.replicate n ())+> x <- select lists+> x++-}+ -- | @unfold step seed@ generates a 'ListT' from a @step@ function and an -- initial @seed@. unfold :: Monad m => (b -> m (Maybe (a, b))) -> b -> ListT m a@@ -560,3 +783,53 @@ instance Monad m => Functor (Step m) where fmap _ Nil = Nil fmap k (Cons x l) = Cons (k x) (fmap k l)++instance MFunctor Step where+ hoist _ Nil = Nil+ hoist f (Cons x xs) = Cons x (hoist f xs)++-- | Similar to 'ZipList' in /base/: a newtype wrapper over 'ListT' that+-- overrides its normal 'Applicative' instance (combine every combination)+-- with one that "zips" outputs together one at a time.+--+-- >>> let xs = do x <- select [1,2,3,4]; liftIO (print x)+-- >>> let ys = do y <- select [5,6]; liftIO (print y)+-- >>> runListT (xs *> ys)+-- 1+-- 5+-- 6+-- 2+-- 5+-- 6+-- 3+-- 5+-- 6+-- 4+-- 5+-- 6+-- >>> runListT (getZipListT (ZipListT xs *> ZipListT ys))+-- 1+-- 5+-- 2+-- 6+-- 3+--+-- Note that the final "3" is printed even though it isn't paired with+-- anything.+--+-- While this can be used to do zipping, it is usually more convenient to+-- just use 'zip'. This is more useful if you are working with a function+-- that expects "an Applicative instance", written to be polymorphic over+-- all Applicatives.+newtype ZipListT m a = ZipListT { getZipListT :: ListT m a }+ deriving (Functor, Alternative, Foldable, Traversable, Floating, Fractional, Num, Semigroup, Monoid)++instance Monad m => Applicative (ZipListT m) where+ pure x = ZipListT go+ where+#if MIN_VERSION_base(4,8,0)+ go = ListT (pure (Cons x go))+#else+ go = ListT (return (Cons x go))+#endif+ ZipListT fs <*> ZipListT xs = ZipListT (fmap (uncurry ($)) (zip fs xs))