{-# LANGUAGE MonadComprehensions #-} -- | Utilities related to Monad and Applicative classes -- Mostly for backwards compatibility. module GHC.Utils.Monad ( Applicative(..) , (<$>) , MonadFix(..) , MonadIO(..) , zipWith3M, zipWith3M_, zipWith4M, zipWithAndUnzipM , mapAndUnzipM, mapAndUnzip3M, mapAndUnzip4M, mapAndUnzip5M , mapAccumLM , mapSndM , concatMapM , mapMaybeM , anyM, allM, orM , foldlM, foldlM_, foldrM , whenM, unlessM , filterOutM , partitionM ) where ------------------------------------------------------------------------------- -- Imports ------------------------------------------------------------------------------- import GHC.Prelude import Control.Monad import Control.Monad.Fix import Control.Monad.IO.Class import Control.Monad.Trans.State.Strict (StateT (..)) import Data.Foldable (sequenceA_, foldlM, foldrM) import Data.List (unzip4, unzip5, zipWith4) import Data.List.NonEmpty (NonEmpty (..)) import Data.Tuple (swap) ------------------------------------------------------------------------------- -- Common functions -- These are used throughout the compiler ------------------------------------------------------------------------------- {- Note [Inline @zipWithNM@ functions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The inline principle for 'zipWith3M', 'zipWith4M' and 'zipWith3M_' is the same as for 'zipWithM' and 'zipWithM_' in "Control.Monad", see Note [Fusion for zipN/zipWithN] in GHC/List.hs for more details. The 'zipWithM'/'zipWithM_' functions are inlined so that the `zipWith` and `sequenceA` functions with which they are defined have an opportunity to fuse. Furthermore, 'zipWith3M'/'zipWith4M' and 'zipWith3M_' have been explicitly rewritten in a non-recursive way similarly to 'zipWithM'/'zipWithM_', and for more than just uniformity: after [D5241](https://phabricator.haskell.org/D5241) for issue #14037, all @zipN@/@zipWithN@ functions fuse, meaning 'zipWith3M'/'zipWIth4M' and 'zipWith3M_'@ now behave like 'zipWithM' and 'zipWithM_', respectively, with regards to fusion. As such, since there are not any differences between 2-ary 'zipWithM'/ 'zipWithM_' and their n-ary counterparts below aside from the number of arguments, the `INLINE` pragma should be replicated in the @zipWithNM@ functions below as well. -} zipWith3M :: Monad m => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m [d] {-# INLINE zipWith3M #-} -- Inline so that fusion with 'zipWith3' and 'sequenceA' has a chance to fire. -- See Note [Inline @zipWithNM@ functions] above. zipWith3M :: forall (m :: * -> *) a b c d. Monad m => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m [d] zipWith3M a -> b -> c -> m d f [a] xs [b] ys [c] zs = [m d] -> m [d] forall (t :: * -> *) (f :: * -> *) a. (Traversable t, Applicative f) => t (f a) -> f (t a) forall (f :: * -> *) a. Applicative f => [f a] -> f [a] sequenceA ((a -> b -> c -> m d) -> [a] -> [b] -> [c] -> [m d] forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] zipWith3 a -> b -> c -> m d f [a] xs [b] ys [c] zs) zipWith3M_ :: Monad m => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m () {-# INLINE zipWith3M_ #-} -- Inline so that fusion with 'zipWith4' and 'sequenceA' has a chance to fire. -- See Note [Inline @zipWithNM@ functions] above. zipWith3M_ :: forall (m :: * -> *) a b c d. Monad m => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m () zipWith3M_ a -> b -> c -> m d f [a] xs [b] ys [c] zs = [m d] -> m () forall (t :: * -> *) (f :: * -> *) a. (Foldable t, Applicative f) => t (f a) -> f () sequenceA_ ((a -> b -> c -> m d) -> [a] -> [b] -> [c] -> [m d] forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] zipWith3 a -> b -> c -> m d f [a] xs [b] ys [c] zs) zipWith4M :: Monad m => (a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> m [e] {-# INLINE zipWith4M #-} -- Inline so that fusion with 'zipWith5' and 'sequenceA' has a chance to fire. -- See Note [Inline @zipWithNM@ functions] above. zipWith4M :: forall (m :: * -> *) a b c d e. Monad m => (a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> m [e] zipWith4M a -> b -> c -> d -> m e f [a] xs [b] ys [c] ws [d] zs = [m e] -> m [e] forall (t :: * -> *) (f :: * -> *) a. (Traversable t, Applicative f) => t (f a) -> f (t a) forall (f :: * -> *) a. Applicative f => [f a] -> f [a] sequenceA ((a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> [m e] forall a b c d e. (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e] zipWith4 a -> b -> c -> d -> m e f [a] xs [b] ys [c] ws [d] zs) zipWithAndUnzipM :: Monad m => (a -> b -> m (c, d)) -> [a] -> [b] -> m ([c], [d]) {-# INLINABLE zipWithAndUnzipM #-} -- this allows specialization to a given monad zipWithAndUnzipM :: forall (m :: * -> *) a b c d. Monad m => (a -> b -> m (c, d)) -> [a] -> [b] -> m ([c], [d]) zipWithAndUnzipM a -> b -> m (c, d) f (a x:[a] xs) (b y:[b] ys) = do { (c c, d d) <- a -> b -> m (c, d) f a x b y ; ([c] cs, [d] ds) <- (a -> b -> m (c, d)) -> [a] -> [b] -> m ([c], [d]) forall (m :: * -> *) a b c d. Monad m => (a -> b -> m (c, d)) -> [a] -> [b] -> m ([c], [d]) zipWithAndUnzipM a -> b -> m (c, d) f [a] xs [b] ys ; ([c], [d]) -> m ([c], [d]) forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return (c cc -> [c] -> [c] forall a. a -> [a] -> [a] :[c] cs, d dd -> [d] -> [d] forall a. a -> [a] -> [a] :[d] ds) } zipWithAndUnzipM a -> b -> m (c, d) _ [a] _ [b] _ = ([c], [d]) -> m ([c], [d]) forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return ([], []) {- Note [Inline @mapAndUnzipNM@ functions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The inline principle is the same as 'mapAndUnzipM' in "Control.Monad". The 'mapAndUnzipM' function is inlined so that the `unzip` and `traverse` functions with which it is defined have an opportunity to fuse, see Note [Inline @unzipN@ functions] in Data/OldList.hs for more details. Furthermore, the @mapAndUnzipNM@ functions have been explicitly rewritten in a non-recursive way similarly to 'mapAndUnzipM', and for more than just uniformity: after [D5249](https://phabricator.haskell.org/D5249) for Trac ticket #14037, all @unzipN@ functions fuse, meaning 'mapAndUnzip3M', 'mapAndUnzip4M' and 'mapAndUnzip5M' now behave like 'mapAndUnzipM' with regards to fusion. As such, since there are not any differences between 2-ary 'mapAndUnzipM' and its n-ary counterparts below aside from the number of arguments, the `INLINE` pragma should be replicated in the @mapAndUnzipNM@ functions below as well. -} -- | mapAndUnzipM for triples mapAndUnzip3M :: Monad m => (a -> m (b,c,d)) -> [a] -> m ([b],[c],[d]) {-# INLINE mapAndUnzip3M #-} -- Inline so that fusion with 'unzip3' and 'traverse' has a chance to fire. -- See Note [Inline @mapAndUnzipNM@ functions] above. mapAndUnzip3M :: forall (m :: * -> *) a b c d. Monad m => (a -> m (b, c, d)) -> [a] -> m ([b], [c], [d]) mapAndUnzip3M a -> m (b, c, d) f [a] xs = [(b, c, d)] -> ([b], [c], [d]) forall a b c. [(a, b, c)] -> ([a], [b], [c]) unzip3 ([(b, c, d)] -> ([b], [c], [d])) -> m [(b, c, d)] -> m ([b], [c], [d]) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> (a -> m (b, c, d)) -> [a] -> m [(b, c, d)] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> [a] -> f [b] traverse a -> m (b, c, d) f [a] xs mapAndUnzip4M :: Monad m => (a -> m (b,c,d,e)) -> [a] -> m ([b],[c],[d],[e]) {-# INLINE mapAndUnzip4M #-} -- Inline so that fusion with 'unzip4' and 'traverse' has a chance to fire. -- See Note [Inline @mapAndUnzipNM@ functions] above. mapAndUnzip4M :: forall (m :: * -> *) a b c d e. Monad m => (a -> m (b, c, d, e)) -> [a] -> m ([b], [c], [d], [e]) mapAndUnzip4M a -> m (b, c, d, e) f [a] xs = [(b, c, d, e)] -> ([b], [c], [d], [e]) forall a b c d. [(a, b, c, d)] -> ([a], [b], [c], [d]) unzip4 ([(b, c, d, e)] -> ([b], [c], [d], [e])) -> m [(b, c, d, e)] -> m ([b], [c], [d], [e]) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> (a -> m (b, c, d, e)) -> [a] -> m [(b, c, d, e)] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> [a] -> f [b] traverse a -> m (b, c, d, e) f [a] xs mapAndUnzip5M :: Monad m => (a -> m (b,c,d,e,f)) -> [a] -> m ([b],[c],[d],[e],[f]) {-# INLINE mapAndUnzip5M #-} -- Inline so that fusion with 'unzip5' and 'traverse' has a chance to fire. -- See Note [Inline @mapAndUnzipNM@ functions] above. mapAndUnzip5M :: forall (m :: * -> *) a b c d e f. Monad m => (a -> m (b, c, d, e, f)) -> [a] -> m ([b], [c], [d], [e], [f]) mapAndUnzip5M a -> m (b, c, d, e, f) f [a] xs = [(b, c, d, e, f)] -> ([b], [c], [d], [e], [f]) forall a b c d e. [(a, b, c, d, e)] -> ([a], [b], [c], [d], [e]) unzip5 ([(b, c, d, e, f)] -> ([b], [c], [d], [e], [f])) -> m [(b, c, d, e, f)] -> m ([b], [c], [d], [e], [f]) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b <$> (a -> m (b, c, d, e, f)) -> [a] -> m [(b, c, d, e, f)] forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> [a] -> f [b] traverse a -> m (b, c, d, e, f) f [a] xs -- TODO: mapAccumLM is used in many places. Surely most of -- these don't actually want to be lazy. We should add a strict -- variant and use it where appropriate. -- | Monadic version of mapAccumL mapAccumLM :: (Monad m, Traversable t) => (acc -> x -> m (acc, y)) -- ^ combining function -> acc -- ^ initial state -> t x -- ^ inputs -> m (acc, t y) -- ^ final state, outputs {-# INLINE [1] mapAccumLM #-} -- INLINE pragma. mapAccumLM is called in inner loops. Like 'map', -- we inline it so that we can take advantage of knowing 'f'. -- This makes a few percent difference (in compiler allocations) -- when compiling perf/compiler/T9675 mapAccumLM :: forall (m :: * -> *) (t :: * -> *) acc x y. (Monad m, Traversable t) => (acc -> x -> m (acc, y)) -> acc -> t x -> m (acc, t y) mapAccumLM acc -> x -> m (acc, y) f acc s = ((t y, acc) -> (acc, t y)) -> m (t y, acc) -> m (acc, t y) forall a b. (a -> b) -> m a -> m b forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap (t y, acc) -> (acc, t y) forall a b. (a, b) -> (b, a) swap (m (t y, acc) -> m (acc, t y)) -> (t x -> m (t y, acc)) -> t x -> m (acc, t y) forall b c a. (b -> c) -> (a -> b) -> a -> c . (StateT acc m (t y) -> acc -> m (t y, acc)) -> acc -> StateT acc m (t y) -> m (t y, acc) forall a b c. (a -> b -> c) -> b -> a -> c flip StateT acc m (t y) -> acc -> m (t y, acc) forall s (m :: * -> *) a. StateT s m a -> s -> m (a, s) runStateT acc s (StateT acc m (t y) -> m (t y, acc)) -> (t x -> StateT acc m (t y)) -> t x -> m (t y, acc) forall b c a. (b -> c) -> (a -> b) -> a -> c . (x -> StateT acc m y) -> t x -> StateT acc m (t y) forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> t a -> f (t b) traverse x -> StateT acc m y f' where f' :: x -> StateT acc m y f' = (acc -> m (y, acc)) -> StateT acc m y forall s (m :: * -> *) a. (s -> m (a, s)) -> StateT s m a StateT ((acc -> m (y, acc)) -> StateT acc m y) -> (x -> acc -> m (y, acc)) -> x -> StateT acc m y forall b c a. (b -> c) -> (a -> b) -> a -> c . ((m (acc, y) -> m (y, acc)) -> (acc -> m (acc, y)) -> acc -> m (y, acc) forall a b. (a -> b) -> (acc -> a) -> acc -> b forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap ((m (acc, y) -> m (y, acc)) -> (acc -> m (acc, y)) -> acc -> m (y, acc)) -> (((acc, y) -> (y, acc)) -> m (acc, y) -> m (y, acc)) -> ((acc, y) -> (y, acc)) -> (acc -> m (acc, y)) -> acc -> m (y, acc) forall b c a. (b -> c) -> (a -> b) -> a -> c . ((acc, y) -> (y, acc)) -> m (acc, y) -> m (y, acc) forall a b. (a -> b) -> m a -> m b forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap) (acc, y) -> (y, acc) forall a b. (a, b) -> (b, a) swap ((acc -> m (acc, y)) -> acc -> m (y, acc)) -> (x -> acc -> m (acc, y)) -> x -> acc -> m (y, acc) forall b c a. (b -> c) -> (a -> b) -> a -> c . (acc -> x -> m (acc, y)) -> x -> acc -> m (acc, y) forall a b c. (a -> b -> c) -> b -> a -> c flip acc -> x -> m (acc, y) f {-# RULES "mapAccumLM/List" mapAccumLM = mapAccumLM_List #-} {-# RULES "mapAccumLM/NonEmpty" mapAccumLM = mapAccumLM_NonEmpty #-} mapAccumLM_List :: Monad m => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y]) {-# INLINE mapAccumLM_List #-} mapAccumLM_List :: forall (m :: * -> *) acc x y. Monad m => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y]) mapAccumLM_List acc -> x -> m (acc, y) f acc s = acc -> [x] -> m (acc, [y]) go acc s where go :: acc -> [x] -> m (acc, [y]) go acc s (x x:[x] xs) = do (acc s1, y x') <- acc -> x -> m (acc, y) f acc s x x (acc s2, [y] xs') <- acc -> [x] -> m (acc, [y]) go acc s1 [x] xs (acc, [y]) -> m (acc, [y]) forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return (acc s2, y x' y -> [y] -> [y] forall a. a -> [a] -> [a] : [y] xs') go acc s [] = (acc, [y]) -> m (acc, [y]) forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return (acc s, []) mapAccumLM_NonEmpty :: Monad m => (acc -> x -> m (acc, y)) -> acc -> NonEmpty x -> m (acc, NonEmpty y) {-# INLINE mapAccumLM_NonEmpty #-} mapAccumLM_NonEmpty :: forall (m :: * -> *) acc x y. Monad m => (acc -> x -> m (acc, y)) -> acc -> NonEmpty x -> m (acc, NonEmpty y) mapAccumLM_NonEmpty acc -> x -> m (acc, y) f acc s (x x:|[x] xs) = [(acc s2, y x'y -> [y] -> NonEmpty y forall a. a -> [a] -> NonEmpty a :|[y] xs') | (acc s1, y x') <- acc -> x -> m (acc, y) f acc s x x, (acc s2, [y] xs') <- (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y]) forall (m :: * -> *) acc x y. Monad m => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y]) mapAccumLM_List acc -> x -> m (acc, y) f acc s1 [x] xs] -- | Monadic version of mapSnd mapSndM :: (Applicative m, Traversable f) => (b -> m c) -> f (a,b) -> m (f (a,c)) mapSndM :: forall (m :: * -> *) (f :: * -> *) b c a. (Applicative m, Traversable f) => (b -> m c) -> f (a, b) -> m (f (a, c)) mapSndM = ((a, b) -> m (a, c)) -> f (a, b) -> m (f (a, c)) forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> f a -> f (f b) traverse (((a, b) -> m (a, c)) -> f (a, b) -> m (f (a, c))) -> ((b -> m c) -> (a, b) -> m (a, c)) -> (b -> m c) -> f (a, b) -> m (f (a, c)) forall b c a. (b -> c) -> (a -> b) -> a -> c . (b -> m c) -> (a, b) -> m (a, c) forall (t :: * -> *) (f :: * -> *) a b. (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> (a, a) -> f (a, b) traverse -- | Monadic version of concatMap concatMapM :: (Monad m, Traversable f) => (a -> m [b]) -> f a -> m [b] concatMapM :: forall (m :: * -> *) (f :: * -> *) a b. (Monad m, Traversable f) => (a -> m [b]) -> f a -> m [b] concatMapM a -> m [b] f f a xs = (f [b] -> [b]) -> m (f [b]) -> m [b] forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r liftM f [b] -> [b] forall (t :: * -> *) a. Foldable t => t [a] -> [a] concat ((a -> m [b]) -> f a -> m (f [b]) forall (t :: * -> *) (m :: * -> *) a b. (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b) forall (m :: * -> *) a b. Monad m => (a -> m b) -> f a -> m (f b) mapM a -> m [b] f f a xs) {-# INLINE concatMapM #-} -- It's better to inline to inline this than to specialise -- concatMapM :: (Monad m) => (a -> m [b]) -> [a] -> m [b] -- Inlining cuts compiler allocation by around 1% -- | Applicative version of mapMaybe mapMaybeM :: Applicative m => (a -> m (Maybe b)) -> [a] -> m [b] mapMaybeM :: forall (m :: * -> *) a b. Applicative m => (a -> m (Maybe b)) -> [a] -> m [b] mapMaybeM a -> m (Maybe b) f = (a -> m [b] -> m [b]) -> m [b] -> [a] -> m [b] forall a b. (a -> b -> b) -> b -> [a] -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> m [b] -> m [b] g ([b] -> m [b] forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure []) where g :: a -> m [b] -> m [b] g a a = (Maybe b -> [b] -> [b]) -> m (Maybe b) -> m [b] -> m [b] forall a b c. (a -> b -> c) -> m a -> m b -> m c forall (f :: * -> *) a b c. Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 (([b] -> [b]) -> (b -> [b] -> [b]) -> Maybe b -> [b] -> [b] forall b a. b -> (a -> b) -> Maybe a -> b maybe [b] -> [b] forall a. a -> a id (:)) (a -> m (Maybe b) f a a) -- | Monadic version of 'any', aborts the computation at the first @True@ value anyM :: (Monad m, Foldable f) => (a -> m Bool) -> f a -> m Bool anyM :: forall (m :: * -> *) (f :: * -> *) a. (Monad m, Foldable f) => (a -> m Bool) -> f a -> m Bool anyM a -> m Bool f = (a -> m Bool -> m Bool) -> m Bool -> f a -> m Bool forall a b. (a -> b -> b) -> b -> f a -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (m Bool -> m Bool -> m Bool forall (m :: * -> *). Monad m => m Bool -> m Bool -> m Bool orM (m Bool -> m Bool -> m Bool) -> (a -> m Bool) -> a -> m Bool -> m Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> m Bool f) (Bool -> m Bool forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure Bool False) -- | Monad version of 'all', aborts the computation at the first @False@ value allM :: (Monad m, Foldable f) => (a -> m Bool) -> f a -> m Bool allM :: forall (m :: * -> *) (f :: * -> *) a. (Monad m, Foldable f) => (a -> m Bool) -> f a -> m Bool allM a -> m Bool f = (a -> m Bool -> m Bool) -> m Bool -> f a -> m Bool forall a b. (a -> b -> b) -> b -> f a -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (m Bool -> m Bool -> m Bool forall (m :: * -> *). Monad m => m Bool -> m Bool -> m Bool andM (m Bool -> m Bool -> m Bool) -> (a -> m Bool) -> a -> m Bool -> m Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> m Bool f) (Bool -> m Bool forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure Bool True) -- | Monadic version of or orM :: Monad m => m Bool -> m Bool -> m Bool orM :: forall (m :: * -> *). Monad m => m Bool -> m Bool -> m Bool orM m Bool m1 m Bool m2 = m Bool m1 m Bool -> (Bool -> m Bool) -> m Bool forall a b. m a -> (a -> m b) -> m b forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b >>= \Bool x -> if Bool x then Bool -> m Bool forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return Bool True else m Bool m2 -- | Monadic version of and andM :: Monad m => m Bool -> m Bool -> m Bool andM :: forall (m :: * -> *). Monad m => m Bool -> m Bool -> m Bool andM m Bool m1 m Bool m2 = m Bool m1 m Bool -> (Bool -> m Bool) -> m Bool forall a b. m a -> (a -> m b) -> m b forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b >>= \Bool x -> if Bool x then m Bool m2 else Bool -> m Bool forall a. a -> m a forall (m :: * -> *) a. Monad m => a -> m a return Bool False -- | Monadic version of foldl that discards its result foldlM_ :: (Monad m, Foldable t) => (a -> b -> m a) -> a -> t b -> m () foldlM_ :: forall (m :: * -> *) (t :: * -> *) a b. (Monad m, Foldable t) => (a -> b -> m a) -> a -> t b -> m () foldlM_ = (a -> b -> m a) -> a -> t b -> m () forall (t :: * -> *) (m :: * -> *) b a. (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m () foldM_ -- | Monadic version of @when@, taking the condition in the monad whenM :: Monad m => m Bool -> m () -> m () whenM :: forall (m :: * -> *). Monad m => m Bool -> m () -> m () whenM m Bool mb m () thing = do { Bool b <- m Bool mb ; Bool -> m () -> m () forall (f :: * -> *). Applicative f => Bool -> f () -> f () when Bool b m () thing } -- | Monadic version of @unless@, taking the condition in the monad unlessM :: Monad m => m Bool -> m () -> m () unlessM :: forall (m :: * -> *). Monad m => m Bool -> m () -> m () unlessM m Bool condM m () acc = do { Bool cond <- m Bool condM ; Bool -> m () -> m () forall (f :: * -> *). Applicative f => Bool -> f () -> f () unless Bool cond m () acc } -- | Like 'filterM', only it reverses the sense of the test. filterOutM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a] filterOutM :: forall (m :: * -> *) a. Applicative m => (a -> m Bool) -> [a] -> m [a] filterOutM a -> m Bool p = (a -> m [a] -> m [a]) -> m [a] -> [a] -> m [a] forall a b. (a -> b -> b) -> b -> [a] -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (\ a x -> (Bool -> [a] -> [a]) -> m Bool -> m [a] -> m [a] forall a b c. (a -> b -> c) -> m a -> m b -> m c forall (f :: * -> *) a b c. Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 (\ Bool flg -> if Bool flg then [a] -> [a] forall a. a -> a id else (a xa -> [a] -> [a] forall a. a -> [a] -> [a] :)) (a -> m Bool p a x)) ([a] -> m [a] forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure []) -- | Monadic version of @partition@ partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a]) partitionM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m ([a], [a]) partitionM a -> m Bool _ [] = ([a], [a]) -> m ([a], [a]) forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure ([], []) partitionM a -> m Bool f (a x:[a] xs) = do Bool res <- a -> m Bool f a x ([a] as,[a] bs) <- (a -> m Bool) -> [a] -> m ([a], [a]) forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m ([a], [a]) partitionM a -> m Bool f [a] xs ([a], [a]) -> m ([a], [a]) forall a. a -> m a forall (f :: * -> *) a. Applicative f => a -> f a pure ([a x | Bool res][a] -> [a] -> [a] forall a. [a] -> [a] -> [a] ++[a] as, [a x | Bool -> Bool not Bool res][a] -> [a] -> [a] forall a. [a] -> [a] -> [a] ++[a] bs) {- Note [The one-shot state monad trick] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Summary: many places in GHC use a state monad, and we really want those functions to be eta-expanded (#18202). The problem ~~~~~~~~~~~ Consider newtype M a = MkM (State -> (State, a)) instance Monad M where mf >>= k = MkM (\s -> case mf of MkM f -> case f s of (s',r) -> case k r of MkM g -> g s') fooM :: Int -> M Int fooM x = g y >>= \r -> h r where y = expensive x Now suppose you say (repeat 20 (fooM 4)), where repeat :: Int -> M Int -> M Int performs its argument n times. You would expect (expensive 4) to be evaluated only once, not 20 times. So foo should have arity 1 (not 2); it should look like this (modulo casts) fooM x = let y = expensive x in \s -> case g y of ... But creating and then repeating, a monadic computation is rare. If you /aren't/ re-using (M a) value, it's /much/ more efficient to make foo have arity 2, thus: fooM x s = case g (expensive x) of ... Why more efficient? Because now foo takes its argument both at once, rather than one at a time, creating a heap-allocated function closure. See https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT for a very good explanation of the issue which led to these optimisations into GHC. The trick ~~~~~~~~~ With state monads like M the general case is that we *aren't* reusing (M a) values so it is much more efficient to avoid allocating a function closure for them. So the state monad trick is a way to keep the monadic syntax but to make GHC eta-expand functions like `fooM`. To do that we use the "oneShot" magic function. Here is the trick: * Define a "smart constructor" mkM :: (State -> (State,a)) -> M a mkM f = MkM (oneShot m) * Never call MkM directly, as a constructor. Instead, always call mkM. And that's it! The magic 'oneShot' function does this transformation: oneShot (\s. e) ==> \s{os}. e which pins a one-shot flag {os} onto the binder 's'. That tells GHC that it can assume the lambda is called only once, and thus can freely float computations in and out of the lambda. To be concrete, let's see what happens to fooM: fooM = \x. g (expensive x) >>= \r -> h r = \x. let mf = g (expensive x) k = \r -> h r in MkM (oneShot (\s -> case mf of MkM' f -> case f s of (s',r) -> case k r of MkM' g -> g s')) -- The MkM' are just newtype casts nt_co = \x. let mf = g (expensive x) k = \r -> h r in (\s{os}. case (mf |> nt_co) s of (s',r) -> (k r) |> nt_co s') |> sym nt_co -- Crucial step: float let-bindings into that \s{os} = \x. (\s{os}. case (g (expensive x) |> nt_co) s of (s',r) -> h r |> nt_co s') |> sym nt_co and voila! fooM has arity 2. The trick is very similar to the built-in "state hack" (see Note [The state-transformer hack] in "GHC.Core.Opt.Arity") but is applicable on a monad-by-monad basis under programmer control. Using pattern synonyms ~~~~~~~~~~~~~~~~~~~~~~ Using a smart constructor is fine, but there is no way to check that we have found *all* uses, especially if the uses escape a single module. A neat (but more sophisticated) alternative is to use pattern synonyms: -- We rename the existing constructor. newtype M a = MkM' (State -> (State, a)) -- The pattern has the old constructor name. pattern MkM f <- MkM' f where MkM f = MkM' (oneShot f) Now we can simply grep to check that there are no uses of MkM' /anywhere/, to guarantee that we have not missed any. (Using the smart constructor alone we still need the data constructor in patterns.) That's the advantage of the pattern-synonym approach, but it is more elaborate. The pattern synonym approach is due to Sebastian Graf (#18238) Do note that for monads for multiple arguments more than one oneShot function might be required. For example in FCode we use: newtype FCode a = FCode' { doFCode :: StgToCmmConfig -> CgState -> (a, CgState) } pattern FCode :: (StgToCmmConfig -> CgState -> (a, CgState)) -> FCode a pattern FCode m <- FCode' m where FCode m = FCode' $ oneShot (\cgInfoDown -> oneShot (\state ->m cgInfoDown state)) Note [INLINE pragmas and (>>)] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A nasty gotcha is described in #20008. In brief, be careful if you get (>>) via its default method: instance Applicative M where pure a = MkM (\s -> (s, a)) (<*>) = ap instance Monad UM where {-# INLINE (>>=) #-} m >>= k = MkM (\s -> blah) Here we define (>>), via its default method, in terms of (>>=). If you do this, be sure to put an INLINE pragma on (>>=), as above. That tells it to inline (>>=) in the RHS of (>>), even when it is applied to only two arguments, which in turn conveys the one-shot info from (>>=) to (>>). Lacking the INLINE, GHC may eta-expand (>>), and with a non-one-shot lambda. #20008 has more discussion. Derived instances ~~~~~~~~~~~~~~~~~ One caveat of both approaches is that derived instances don't use the smart constructor /or/ the pattern synonym. So they won't benefit from the automatic insertion of "oneShot". data M a = MkM' (State -> (State,a)) deriving (Functor) <-- Functor implementation will use MkM'! Conclusion: don't use 'derviving' in these cases. Multi-shot actions (cf #18238) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sometimes we really *do* want computations to be shared! Remember our example (repeat 20 (fooM 4)). See Note [multiShotIO] in GHC.Types.Unique.Supply We can force fooM to have arity 1 using multiShot: fooM :: Int -> M Int fooM x = multiShotM (g y >>= \r -> h r) where y = expensive x multiShotM :: M a -> M a {-# INLINE multiShotM #-} multiShotM (MkM m) = MkM (\s -> inline m s) -- Really uses the data constructor, -- not the smart constructor! Now we can see how fooM optimises (ignoring casts) multiShotM (g y >>= \r -> h r) ==> {inline (>>=)} multiShotM (\s{os}. case g y s of ...) ==> {inline multiShotM} let m = \s{os}. case g y s of ... in \s. inline m s ==> {inline m} \s. (\s{os}. case g y s of ...) s ==> \s. case g y s of ... and voila! the one-shot flag has gone. It's possible that y has been replaced by (expensive x), but full laziness should pull it back out. (This part seems less robust.) The magic `inline` function does two things * It prevents eta reduction. If we wrote just multiShotIO (IO m) = IO (\s -> m s) the lambda would eta-reduce to 'm' and all would be lost. * It helps ensure that 'm' really does inline. Note that 'inline' evaporates in phase 0. See Note [inlineId magic] in GHC.Core.Opt.ConstantFold.match_inline. The INLINE pragma on multiShotM is very important, else the 'inline' call will evaporate when compiling the module that defines 'multiShotM', before it is ever exported. -}