content: {-# LANGUAGE MonadComprehensions #-}
  
  -- | Utilities related to Monad and Applicative classes
  --   Mostly for backwards compatibility.
  
  module GHC.Utils.Monad
          ( Applicative(..)
          , (<$>)
  
          , MonadFix(..)
          , MonadIO(..)
  
          , zipWith3M, zipWith3M_, zipWith4M, zipWithAndUnzipM
          , zipWith3MNE
          , mapAndUnzipM, mapAndUnzip3M, mapAndUnzip4M, mapAndUnzip5M
          , mapAccumLM
          , mapSndM
          , concatMapM
          , mapMaybeM
          , anyM, allM, orM
          , foldlM, foldlM_, foldrM, foldMapM
          , 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.Monoid (Ap (Ap, getAp))
  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 f xs ys zs = sequenceA (zipWith3 f xs ys 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_ f xs ys zs = sequenceA_ (zipWith3 f xs ys 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 f xs ys ws zs = sequenceA (zipWith4 f xs ys ws zs)
  
  zipWithAndUnzipM :: Monad m
                   => (a -> b -> m (c, d)) -> [a] -> [b] -> m ([c], [d])
  {-# INLINABLE zipWithAndUnzipM #-}  -- this allows specialization to a given monad
  zipWithAndUnzipM f (x:xs) (y:ys)
    = do { (c, d) <- f x y
         ; (cs, ds) <- zipWithAndUnzipM f xs ys
         ; return (c:cs, d:ds) }
  zipWithAndUnzipM _ _ _ = return ([], [])
  
  -- | 'zipWith3M' for 'NonEmpty' lists.
  zipWith3MNE :: Monad m
              => (a -> b -> c -> m d)
              -> NonEmpty a -> NonEmpty b -> NonEmpty c -> m (NonEmpty d)
  zipWith3MNE f ~(x :| xs) ~(y :| ys) ~(z :| zs)
    = do { w  <- f x y z
         ; ws <- zipWith3M f xs ys zs
         ; return $ w :| ws }
  
  {-
  
  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 f xs =  unzip3 <$> traverse f 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 f xs =  unzip4 <$> traverse f 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 f xs =  unzip5 <$> traverse f 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 f s = fmap swap . flip runStateT s . traverse f'
    where
      f' = StateT . (fmap . fmap) swap . flip 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 f s = go s
    where
      go s (x:xs) = do
        (s1, x')  <- f s x
        (s2, xs') <- go s1 xs
        return    (s2, x' : xs')
      go s [] = return (s, [])
  
  mapAccumLM_NonEmpty
   :: Monad m
   => (acc -> x -> m (acc, y))
   -> acc -> NonEmpty x -> m (acc, NonEmpty y)
  {-# INLINE mapAccumLM_NonEmpty #-}
  mapAccumLM_NonEmpty f s (x:|xs) =
    [(s2, x':|xs') | (s1, x') <- f s x, (s2, xs') <- mapAccumLM_List f s1 xs]
  
  -- | Monadic version of mapSnd
  mapSndM :: (Applicative m, Traversable f) => (b -> m c) -> f (a,b) -> m (f (a,c))
  mapSndM = traverse . traverse
  
  -- | Monadic version of concatMap
  concatMapM :: (Monad m, Traversable f) => (a -> m [b]) -> f a -> m [b]
  concatMapM f xs = liftM concat (mapM f 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 f = foldr g (pure [])
    where g a = liftA2 (maybe id (:)) (f 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 f = foldr (orM . f) (pure 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 f = foldr (andM . f) (pure True)
  
  -- | Monadic version of or
  orM :: Monad m => m Bool -> m Bool -> m Bool
  orM m1 m2 = m1 >>= \x -> if x then return True else m2
  
  -- | Monadic version of and
  andM :: Monad m => m Bool -> m Bool -> m Bool
  andM m1 m2 = m1 >>= \x -> if x then m2 else return False
  
  -- | Monadic version of foldl that discards its result
  foldlM_ :: (Monad m, Foldable t) => (a -> b -> m a) -> a -> t b -> m ()
  foldlM_ = foldM_
  
  -- | Monadic version of 'foldMap'
  foldMapM :: (Applicative m, Foldable t, Monoid b) => (a -> m b) -> t a -> m b
  foldMapM f = getAp <$> foldMap (Ap . f)
  
  -- | Monadic version of @when@, taking the condition in the monad
  whenM :: Monad m => m Bool -> m () -> m ()
  whenM mb thing = do { b <- mb
                      ; when b thing }
  
  -- | Monadic version of @unless@, taking the condition in the monad
  unlessM :: Monad m => m Bool -> m () -> m ()
  unlessM condM acc = do { cond <- condM
                         ; unless cond acc }
  
  -- | Like 'filterM', only it reverses the sense of the test.
  filterOutM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
  filterOutM p =
    foldr (\ x -> liftA2 (\ flg -> if flg then id else (x:)) (p x)) (pure [])
  
  -- | Monadic version of @partition@
  partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a])
  partitionM _ [] = pure ([], [])
  partitionM f (x:xs) = do
      res <- f x
      (as,bs) <- partitionM f xs
      pure ([x | res]++as, [x | not res]++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.
  -}
  