    {-# LANGUAGE DeriveDataTypeable #-}
    {-# LANGUAGE DeriveGeneric #-}
    {-# LANGUAGE FlexibleInstances #-}
    {-# LANGUAGE UndecidableInstances #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE Rank2Types #-}
    {-# LANGUAGE Safe #-}
    {-# LANGUAGE StandaloneDeriving #-}

    --------------------------------------------------------------------------------
    -- |
    -- \"Applicative Effects in Free Monads\"
    --
    -- Often times, the '(\<*\>)' operator can be more efficient than 'ap'.
    -- Conventional free monads don't provide any means of modeling this.
    -- The free monad can be modified to make use of an underlying applicative.
    -- But it does require some laws, or else the '(\<*\>)' = 'ap' law is broken.
    -- When interpreting this free monad with 'foldFree',
    -- the natural transformation must be an applicative homomorphism.
    -- An applicative homomorphism @hm :: (Applicative f, Applicative g) => f x -> g x@
    -- will satisfy these laws.
    --
    -- * @hm (pure a) = pure a@
    -- * @hm (f \<*\> a) = hm f \<*\> hm a@
    --
    -- This is based on the \"Applicative Effects in Free Monads\" series of articles by Will Fancher
    --
    -- * <http://elvishjerricco.github.io/2016/04/08/applicative-effects-in-free-monads.html Applicative Effects in Free Monads>
    --
    -- * <http://elvishjerricco.github.io/2016/04/13/more-on-applicative-effects-in-free-monads.html More on Applicative Effects in Free Monads>
    --------------------------------------------------------------------------------
    module Control.Monad.Free.Ap
      ( MonadFree(..)
      , Free(..)
      , retract
      , liftF
      , iter
      , iterA
      , iterM
      , hoistFree
      , foldFree
      , toFreeT
      , cutoff
      , unfold
      , unfoldM
      , _Pure, _Free
      ) where

    import Control.Applicative
    import Control.Arrow ((>>>))
    import Control.Monad (liftM, MonadPlus(..), (>=>))
    import Control.Monad.Fix
    import Control.Monad.Trans.Class
    import qualified Control.Monad.Trans.Free.Ap as FreeT
    import Control.Monad.Free.Class
    import Control.Monad.Reader.Class
    import Control.Monad.Writer.Class
    import Control.Monad.State.Class
    import Control.Monad.Error.Class
    import Control.Monad.Cont.Class
    import Data.Functor.Bind
    import Data.Functor.Classes
    import Data.Foldable
    import Data.Profunctor
    import Data.Traversable
    import Data.Semigroup.Foldable
    import Data.Semigroup.Traversable
    import Data.Data
    import GHC.Generics
    import Prelude hiding (foldr)

    -- $setup
    -- >>> import Control.Applicative (Const (..))
    -- >>> import Data.Functor.Identity (Identity (..))
    -- >>> import Data.Monoid (First (..))
    -- >>> import Data.Tagged (Tagged (..))
    -- >>> let preview l x = getFirst (getConst (l (Const . First . Just) x))
    -- >>> let review l x = runIdentity (unTagged (l (Tagged (Identity x))))

    -- | A free monad given an applicative
    data Free f a = Pure a | Free (f (Free f a))
      deriving ((forall x. Free f a -> Rep (Free f a) x)
    -> (forall x. Rep (Free f a) x -> Free f a) -> Generic (Free f a)
    forall x. Rep (Free f a) x -> Free f a
    forall x. Free f a -> Rep (Free f a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall (f :: * -> *) a x. Rep (Free f a) x -> Free f a
    forall (f :: * -> *) a x. Free f a -> Rep (Free f a) x
    $cfrom :: forall (f :: * -> *) a x. Free f a -> Rep (Free f a) x
    from :: forall x. Free f a -> Rep (Free f a) x
    $cto :: forall (f :: * -> *) a x. Rep (Free f a) x -> Free f a
    to :: forall x. Rep (Free f a) x -> Free f a
    Generic, (forall a. Free f a -> Rep1 (Free f) a)
    -> (forall a. Rep1 (Free f) a -> Free f a) -> Generic1 (Free f)
    forall a. Rep1 (Free f) a -> Free f a
    forall a. Free f a -> Rep1 (Free f) a
    forall k (f :: k -> *).
    (forall (a :: k). f a -> Rep1 f a)
    -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
    forall (f :: * -> *) a. Functor f => Rep1 (Free f) a -> Free f a
    forall (f :: * -> *) a. Functor f => Free f a -> Rep1 (Free f) a
    $cfrom1 :: forall (f :: * -> *) a. Functor f => Free f a -> Rep1 (Free f) a
    from1 :: forall a. Free f a -> Rep1 (Free f) a
    $cto1 :: forall (f :: * -> *) a. Functor f => Rep1 (Free f) a -> Free f a
    to1 :: forall a. Rep1 (Free f) a -> Free f a
    Generic1)

    deriving instance
      ( Typeable f
      , Data a, Data (f (Free f a))
      ) => Data (Free f a)

    instance Eq1 f => Eq1 (Free f) where
      liftEq :: forall a b. (a -> b -> Bool) -> Free f a -> Free f b -> Bool
    liftEq a -> b -> Bool
    eq = Free f a -> Free f b -> Bool
    forall {f :: * -> *}. Eq1 f => Free f a -> Free f b -> Bool
    go
        where
          go :: Free f a -> Free f b -> Bool
    go (Pure a
    a)  (Pure b
    b)  = a -> b -> Bool
    eq a
    a b
    b
          go (Free f (Free f a)
    fa) (Free f (Free f b)
    fb) = (Free f a -> Free f b -> Bool)
    -> f (Free f a) -> f (Free f b) -> Bool
    forall a b. (a -> b -> Bool) -> f a -> f b -> Bool
    forall (f :: * -> *) a b.
    Eq1 f =>
    (a -> b -> Bool) -> f a -> f b -> Bool
    liftEq Free f a -> Free f b -> Bool
    go f (Free f a)
    fa f (Free f b)
    fb
          go Free f a
    _ Free f b
    _                 = Bool
    False

    instance (Eq1 f, Eq a) => Eq (Free f a) where
      == :: Free f a -> Free f a -> Bool
    (==) = Free f a -> Free f a -> Bool
    forall (f :: * -> *) a. (Eq1 f, Eq a) => f a -> f a -> Bool
    eq1

    instance Ord1 f => Ord1 (Free f) where
      liftCompare :: forall a b.
    (a -> b -> Ordering) -> Free f a -> Free f b -> Ordering
    liftCompare a -> b -> Ordering
    cmp = Free f a -> Free f b -> Ordering
    forall {f :: * -> *}. Ord1 f => Free f a -> Free f b -> Ordering
    go
        where
          go :: Free f a -> Free f b -> Ordering
    go (Pure a
    a)  (Pure b
    b)  = a -> b -> Ordering
    cmp a
    a b
    b
          go (Pure a
    _)  (Free f (Free f b)
    _)  = Ordering
    LT
          go (Free f (Free f a)
    _)  (Pure b
    _)  = Ordering
    GT
          go (Free f (Free f a)
    fa) (Free f (Free f b)
    fb) = (Free f a -> Free f b -> Ordering)
    -> f (Free f a) -> f (Free f b) -> Ordering
    forall a b. (a -> b -> Ordering) -> f a -> f b -> Ordering
    forall (f :: * -> *) a b.
    Ord1 f =>
    (a -> b -> Ordering) -> f a -> f b -> Ordering
    liftCompare Free f a -> Free f b -> Ordering
    go f (Free f a)
    fa f (Free f b)
    fb

    instance (Ord1 f, Ord a) => Ord (Free f a) where
      compare :: Free f a -> Free f a -> Ordering
    compare = Free f a -> Free f a -> Ordering
    forall (f :: * -> *) a. (Ord1 f, Ord a) => f a -> f a -> Ordering
    compare1

    instance Show1 f => Show1 (Free f) where
      liftShowsPrec :: forall a.
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Free f a -> ShowS
    liftShowsPrec Int -> a -> ShowS
    sp [a] -> ShowS
    sl = Int -> Free f a -> ShowS
    forall {f :: * -> *}. Show1 f => Int -> Free f a -> ShowS
    go
        where
          go :: Int -> Free f a -> ShowS
    go Int
    d (Pure a
    a) = (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
    forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
    showsUnaryWith Int -> a -> ShowS
    sp String
    "Pure" Int
    d a
    a
          go Int
    d (Free f (Free f a)
    fa) = (Int -> f (Free f a) -> ShowS)
    -> String -> Int -> f (Free f a) -> ShowS
    forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
    showsUnaryWith ((Int -> Free f a -> ShowS)
    -> ([Free f a] -> ShowS) -> Int -> f (Free f a) -> ShowS
    forall a.
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
    forall (f :: * -> *) a.
    Show1 f =>
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
    liftShowsPrec Int -> Free f a -> ShowS
    go ((Int -> a -> ShowS) -> ([a] -> ShowS) -> [Free f a] -> ShowS
    forall a.
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Free f a] -> ShowS
    forall (f :: * -> *) a.
    Show1 f =>
    (Int -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS
    liftShowList Int -> a -> ShowS
    sp [a] -> ShowS
    sl)) String
    "Free" Int
    d f (Free f a)
    fa

    instance (Show1 f, Show a) => Show (Free f a) where
      showsPrec :: Int -> Free f a -> ShowS
    showsPrec = Int -> Free f a -> ShowS
    forall (f :: * -> *) a. (Show1 f, Show a) => Int -> f a -> ShowS
    showsPrec1

    instance Read1 f => Read1 (Free f) where
      liftReadsPrec :: forall a. (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Free f a)
    liftReadsPrec Int -> ReadS a
    rp ReadS [a]
    rl = Int -> ReadS (Free f a)
    go
        where
          go :: Int -> ReadS (Free f a)
    go = (String -> ReadS (Free f a)) -> Int -> ReadS (Free f a)
    forall a. (String -> ReadS a) -> Int -> ReadS a
    readsData ((String -> ReadS (Free f a)) -> Int -> ReadS (Free f a))
    -> (String -> ReadS (Free f a)) -> Int -> ReadS (Free f a)
    forall a b. (a -> b) -> a -> b
    $
            (Int -> ReadS a)
    -> String -> (a -> Free f a) -> String -> ReadS (Free f a)
    forall a t.
    (Int -> ReadS a) -> String -> (a -> t) -> String -> ReadS t
    readsUnaryWith Int -> ReadS a
    rp String
    "Pure" a -> Free f a
    forall (f :: * -> *) a. a -> Free f a
    Pure (String -> ReadS (Free f a))
    -> (String -> ReadS (Free f a)) -> String -> ReadS (Free f a)
    forall a. Monoid a => a -> a -> a
    `mappend`
            (Int -> ReadS (f (Free f a)))
    -> String
    -> (f (Free f a) -> Free f a)
    -> String
    -> ReadS (Free f a)
    forall a t.
    (Int -> ReadS a) -> String -> (a -> t) -> String -> ReadS t
    readsUnaryWith ((Int -> ReadS (Free f a))
    -> ReadS [Free f a] -> Int -> ReadS (f (Free f a))
    forall a. (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
    forall (f :: * -> *) a.
    Read1 f =>
    (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
    liftReadsPrec Int -> ReadS (Free f a)
    go ((Int -> ReadS a) -> ReadS [a] -> ReadS [Free f a]
    forall a. (Int -> ReadS a) -> ReadS [a] -> ReadS [Free f a]
    forall (f :: * -> *) a.
    Read1 f =>
    (Int -> ReadS a) -> ReadS [a] -> ReadS [f a]
    liftReadList Int -> ReadS a
    rp ReadS [a]
    rl)) String
    "Free" f (Free f a) -> Free f a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free

    instance (Read1 f, Read a) => Read (Free f a) where
      readsPrec :: Int -> ReadS (Free f a)
    readsPrec = Int -> ReadS (Free f a)
    forall (f :: * -> *) a. (Read1 f, Read a) => Int -> ReadS (f a)
    readsPrec1

    instance Functor f => Functor (Free f) where
      fmap :: forall a b. (a -> b) -> Free f a -> Free f b
    fmap a -> b
    f = Free f a -> Free f b
    forall {f :: * -> *}. Functor f => Free f a -> Free f b
    go where
        go :: Free f a -> Free f b
    go (Pure a
    a)  = b -> Free f b
    forall (f :: * -> *) a. a -> Free f a
    Pure (a -> b
    f a
    a)
        go (Free f (Free f a)
    fa) = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (Free f a -> Free f b
    go (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    fa)
      {-# INLINE fmap #-}

    instance Apply f => Apply (Free f) where
      Pure a -> b
    a  <.> :: forall a b. Free f (a -> b) -> Free f a -> Free f b
    <.> Pure a
    b = b -> Free f b
    forall (f :: * -> *) a. a -> Free f a
    Pure (a -> b
    a a
    b)
      Pure a -> b
    a  <.> Free f (Free f a)
    fb = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ (a -> b) -> Free f a -> Free f b
    forall a b. (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    a (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    fb
      Free f (Free f (a -> b))
    fa <.> Pure a
    b = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ ((a -> b) -> b) -> Free f (a -> b) -> Free f b
    forall a b. (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $ a
    b) (Free f (a -> b) -> Free f b)
    -> f (Free f (a -> b)) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f (a -> b))
    fa
      Free f (Free f (a -> b))
    fa <.> Free f (Free f a)
    fb = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ (Free f (a -> b) -> Free f a -> Free f b)
    -> f (Free f (a -> b)) -> f (Free f a -> Free f b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Free f (a -> b) -> Free f a -> Free f b
    forall a b. Free f (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    (<.>) f (Free f (a -> b))
    fa f (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    <.> f (Free f a)
    fb

    instance Applicative f => Applicative (Free f) where
      pure :: forall a. a -> Free f a
    pure = a -> Free f a
    forall (f :: * -> *) a. a -> Free f a
    Pure
      {-# INLINE pure #-}
      Pure a -> b
    a <*> :: forall a b. Free f (a -> b) -> Free f a -> Free f b
    <*> Pure a
    b = b -> Free f b
    forall (f :: * -> *) a. a -> Free f a
    Pure (b -> Free f b) -> b -> Free f b
    forall a b. (a -> b) -> a -> b
    $ a -> b
    a a
    b
      Pure a -> b
    a <*> Free f (Free f a)
    mb = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ (a -> b) -> Free f a -> Free f b
    forall a b. (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    a (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    mb
      Free f (Free f (a -> b))
    ma <*> Pure a
    b = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ ((a -> b) -> b) -> Free f (a -> b) -> Free f b
    forall a b. (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $ a
    b) (Free f (a -> b) -> Free f b)
    -> f (Free f (a -> b)) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f (a -> b))
    ma
      Free f (Free f (a -> b))
    ma <*> Free f (Free f a)
    mb = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (Free f b) -> Free f b
    forall a b. (a -> b) -> a -> b
    $ (Free f (a -> b) -> Free f a -> Free f b)
    -> f (Free f (a -> b)) -> f (Free f a -> Free f b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Free f (a -> b) -> Free f a -> Free f b
    forall a b. Free f (a -> b) -> Free f a -> Free f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    (<*>) f (Free f (a -> b))
    ma f (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> f (Free f a)
    mb

    instance Apply f => Bind (Free f) where
      Pure a
    a >>- :: forall a b. Free f a -> (a -> Free f b) -> Free f b
    >>- a -> Free f b
    f = a -> Free f b
    f a
    a
      Free f (Free f a)
    m >>- a -> Free f b
    f = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free ((Free f a -> (a -> Free f b) -> Free f b
    forall a b. Free f a -> (a -> Free f b) -> Free f b
    forall (m :: * -> *) a b. Bind m => m a -> (a -> m b) -> m b
    >>- a -> Free f b
    f) (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    m)

    instance Applicative f => Monad (Free f) where
      return :: forall a. a -> Free f a
    return = a -> Free f a
    forall a. a -> Free f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      {-# INLINE return #-}
      Pure a
    a >>= :: forall a b. Free f a -> (a -> Free f b) -> Free f b
    >>= a -> Free f b
    f = a -> Free f b
    f a
    a
      Free f (Free f a)
    m >>= a -> Free f b
    f = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free ((Free f a -> (a -> Free f b) -> Free f b
    forall a b. Free f a -> (a -> Free f b) -> Free f b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= a -> Free f b
    f) (Free f a -> Free f b) -> f (Free f a) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    m)

    instance Applicative f => MonadFix (Free f) where
      mfix :: forall a. (a -> Free f a) -> Free f a
    mfix a -> Free f a
    f = Free f a
    a where a :: Free f a
    a = a -> Free f a
    f (Free f a -> a
    forall {f :: * -> *} {a}. Free f a -> a
    impure Free f a
    a); impure :: Free f a -> a
    impure (Pure a
    x) = a
    x; impure (Free f (Free f a)
    _) = String -> a
    forall a. HasCallStack => String -> a
    error String
    "mfix (Free f): Free"

    -- | This violates the Alternative laws, handle with care.
    instance Alternative v => Alternative (Free v) where
      empty :: forall a. Free v a
    empty = v (Free v a) -> Free v a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free v (Free v a)
    forall a. v a
    forall (f :: * -> *) a. Alternative f => f a
    empty
      {-# INLINE empty #-}
      Free v a
    a <|> :: forall a. Free v a -> Free v a -> Free v a
    <|> Free v a
    b = v (Free v a) -> Free v a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (Free v a -> v (Free v a)
    forall a. a -> v a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Free v a
    a v (Free v a) -> v (Free v a) -> v (Free v a)
    forall a. v a -> v a -> v a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Free v a -> v (Free v a)
    forall a. a -> v a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Free v a
    b)
      {-# INLINE (<|>) #-}

    -- | This violates the MonadPlus laws, handle with care.
    instance MonadPlus v => MonadPlus (Free v) where
      mzero :: forall a. Free v a
    mzero = v (Free v a) -> Free v a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free v (Free v a)
    forall a. v a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
      {-# INLINE mzero #-}
      Free v a
    a mplus :: forall a. Free v a -> Free v a -> Free v a
    `mplus` Free v a
    b = v (Free v a) -> Free v a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (Free v a -> v (Free v a)
    forall a. a -> v a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Free v a
    a v (Free v a) -> v (Free v a) -> v (Free v a)
    forall a. v a -> v a -> v a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` Free v a -> v (Free v a)
    forall a. a -> v a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Free v a
    b)
      {-# INLINE mplus #-}

    -- | This is not a true monad transformer. It is only a monad transformer \"up to 'retract'\".
    instance MonadTrans Free where
      lift :: forall (m :: * -> *) a. Monad m => m a -> Free m a
    lift = m (Free m a) -> Free m a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (m (Free m a) -> Free m a)
    -> (m a -> m (Free m a)) -> m a -> Free m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Free m a) -> m a -> m (Free m a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> Free m a
    forall (f :: * -> *) a. a -> Free f a
    Pure
      {-# INLINE lift #-}

    instance Foldable f => Foldable (Free f) where
      foldMap :: forall m a. Monoid m => (a -> m) -> Free f a -> m
    foldMap a -> m
    f = Free f a -> m
    forall {t :: * -> *}. Foldable t => Free t a -> m
    go where
        go :: Free t a -> m
    go (Pure a
    a) = a -> m
    f a
    a
        go (Free t (Free t a)
    fa) = (Free t a -> m) -> t (Free t a) -> m
    forall m a. Monoid m => (a -> m) -> t a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap Free t a -> m
    go t (Free t a)
    fa
      {-# INLINE foldMap #-}

      foldr :: forall a b. (a -> b -> b) -> b -> Free f a -> b
    foldr a -> b -> b
    f = b -> Free f a -> b
    forall {t :: * -> *}. Foldable t => b -> Free t a -> b
    go where
        go :: b -> Free t a -> b
    go b
    r Free t a
    free =
          case Free t a
    free of
            Pure a
    a -> a -> b -> b
    f a
    a b
    r
            Free t (Free t a)
    fa -> (Free t a -> b -> b) -> b -> t (Free t a) -> b
    forall a b. (a -> b -> b) -> b -> t a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr ((b -> Free t a -> b) -> Free t a -> b -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip b -> Free t a -> b
    go) b
    r t (Free t a)
    fa
      {-# INLINE foldr #-}

      foldl' :: forall b a. (b -> a -> b) -> b -> Free f a -> b
    foldl' b -> a -> b
    f = b -> Free f a -> b
    forall {t :: * -> *}. Foldable t => b -> Free t a -> b
    go where
        go :: b -> Free t a -> b
    go b
    r Free t a
    free =
          case Free t a
    free of
            Pure a
    a -> b -> a -> b
    f b
    r a
    a
            Free t (Free t a)
    fa -> (b -> Free t a -> b) -> b -> t (Free t a) -> b
    forall b a. (b -> a -> b) -> b -> t a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' b -> Free t a -> b
    go b
    r t (Free t a)
    fa
      {-# INLINE foldl' #-}

    instance Foldable1 f => Foldable1 (Free f) where
      foldMap1 :: forall m a. Semigroup m => (a -> m) -> Free f a -> m
    foldMap1 a -> m
    f = Free f a -> m
    forall {t :: * -> *}. Foldable1 t => Free t a -> m
    go where
        go :: Free t a -> m
    go (Pure a
    a) = a -> m
    f a
    a
        go (Free t (Free t a)
    fa) = (Free t a -> m) -> t (Free t a) -> m
    forall m a. Semigroup m => (a -> m) -> t a -> m
    forall (t :: * -> *) m a.
    (Foldable1 t, Semigroup m) =>
    (a -> m) -> t a -> m
    foldMap1 Free t a -> m
    go t (Free t a)
    fa
      {-# INLINE foldMap1 #-}

    instance Traversable f => Traversable (Free f) where
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Free f a -> f (Free f b)
    traverse a -> f b
    f = Free f a -> f (Free f b)
    forall {f :: * -> *}. Traversable f => Free f a -> f (Free f b)
    go where
        go :: Free f a -> f (Free f b)
    go (Pure a
    a) = b -> Free f b
    forall (f :: * -> *) a. a -> Free f a
    Pure (b -> Free f b) -> f b -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> f b
    f a
    a
        go (Free f (Free f a)
    fa) = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (f (Free f b)) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Free f a -> f (Free f b)) -> f (Free f a) -> f (f (Free f b))
    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 Free f a -> f (Free f b)
    go f (Free f a)
    fa
      {-# INLINE traverse #-}

    instance Traversable1 f => Traversable1 (Free f) where
      traverse1 :: forall (f :: * -> *) a b.
    Apply f =>
    (a -> f b) -> Free f a -> f (Free f b)
    traverse1 a -> f b
    f = Free f a -> f (Free f b)
    forall {f :: * -> *}. Traversable1 f => Free f a -> f (Free f b)
    go where
        go :: Free f a -> f (Free f b)
    go (Pure a
    a) = b -> Free f b
    forall (f :: * -> *) a. a -> Free f a
    Pure (b -> Free f b) -> f b -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> f b
    f a
    a
        go (Free f (Free f a)
    fa) = f (Free f b) -> Free f b
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f b) -> Free f b) -> f (f (Free f b)) -> f (Free f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Free f a -> f (Free f b)) -> f (Free f a) -> f (f (Free f b))
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable1 t, Apply f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b. Apply f => (a -> f b) -> f a -> f (f b)
    traverse1 Free f a -> f (Free f b)
    go f (Free f a)
    fa
      {-# INLINE traverse1 #-}

    instance MonadWriter e m => MonadWriter e (Free m) where
      tell :: e -> Free m ()
    tell = m () -> Free m ()
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m () -> Free m ()) -> (e -> m ()) -> e -> Free m ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> m ()
    forall w (m :: * -> *). MonadWriter w m => w -> m ()
    tell
      {-# INLINE tell #-}
      listen :: forall a. Free m a -> Free m (a, e)
    listen = m (a, e) -> Free m (a, e)
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (a, e) -> Free m (a, e))
    -> (Free m a -> m (a, e)) -> Free m a -> Free m (a, e)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m a -> m (a, e)
    forall a. m a -> m (a, e)
    forall w (m :: * -> *) a. MonadWriter w m => m a -> m (a, w)
    listen (m a -> m (a, e)) -> (Free m a -> m a) -> Free m a -> m (a, e)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Free m a -> m a
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract
      {-# INLINE listen #-}
      pass :: forall a. Free m (a, e -> e) -> Free m a
    pass = m a -> Free m a
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> Free m a)
    -> (Free m (a, e -> e) -> m a) -> Free m (a, e -> e) -> Free m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (a, e -> e) -> m a
    forall a. m (a, e -> e) -> m a
    forall w (m :: * -> *) a. MonadWriter w m => m (a, w -> w) -> m a
    pass (m (a, e -> e) -> m a)
    -> (Free m (a, e -> e) -> m (a, e -> e))
    -> Free m (a, e -> e)
    -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Free m (a, e -> e) -> m (a, e -> e)
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract
      {-# INLINE pass #-}

    instance MonadReader e m => MonadReader e (Free m) where
      ask :: Free m e
    ask = m e -> Free m e
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m e
    forall r (m :: * -> *). MonadReader r m => m r
    ask
      {-# INLINE ask #-}
      local :: forall a. (e -> e) -> Free m a -> Free m a
    local e -> e
    f = m a -> Free m a
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> Free m a) -> (Free m a -> m a) -> Free m a -> Free m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (e -> e) -> m a -> m a
    forall a. (e -> e) -> m a -> m a
    forall r (m :: * -> *) a. MonadReader r m => (r -> r) -> m a -> m a
    local e -> e
    f (m a -> m a) -> (Free m a -> m a) -> Free m a -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Free m a -> m a
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract
      {-# INLINE local #-}

    instance MonadState s m => MonadState s (Free m) where
      get :: Free m s
    get = m s -> Free m s
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m s
    forall s (m :: * -> *). MonadState s m => m s
    get
      {-# INLINE get #-}
      put :: s -> Free m ()
    put s
    s = m () -> Free m ()
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (s -> m ()
    forall s (m :: * -> *). MonadState s m => s -> m ()
    put s
    s)
      {-# INLINE put #-}

    instance MonadError e m => MonadError e (Free m) where
      throwError :: forall a. e -> Free m a
    throwError = m a -> Free m a
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> Free m a) -> (e -> m a) -> e -> Free m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> m a
    forall a. e -> m a
    forall e (m :: * -> *) a. MonadError e m => e -> m a
    throwError
      {-# INLINE throwError #-}
      catchError :: forall a. Free m a -> (e -> Free m a) -> Free m a
    catchError Free m a
    as e -> Free m a
    f = m a -> Free m a
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> (e -> m a) -> m a
    forall a. m a -> (e -> m a) -> m a
    forall e (m :: * -> *) a.
    MonadError e m =>
    m a -> (e -> m a) -> m a
    catchError (Free m a -> m a
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract Free m a
    as) (Free m a -> m a
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract (Free m a -> m a) -> (e -> Free m a) -> e -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> Free m a
    f))
      {-# INLINE catchError #-}

    instance MonadCont m => MonadCont (Free m) where
      callCC :: forall a b. ((a -> Free m b) -> Free m a) -> Free m a
    callCC (a -> Free m b) -> Free m a
    f = m a -> Free m a
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (((a -> m b) -> m a) -> m a
    forall a b. ((a -> m b) -> m a) -> m a
    forall (m :: * -> *) a b. MonadCont m => ((a -> m b) -> m a) -> m a
    callCC (Free m a -> m a
    forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract (Free m a -> m a) -> ((a -> m b) -> Free m a) -> (a -> m b) -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Free m b) -> Free m a
    f ((a -> Free m b) -> Free m a)
    -> ((a -> m b) -> a -> Free m b) -> (a -> m b) -> Free m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (m b -> Free m b) -> (a -> m b) -> a -> Free m b
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM m b -> Free m b
    forall (m :: * -> *) a. Monad m => m a -> Free m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift))
      {-# INLINE callCC #-}

    instance Applicative f => MonadFree f (Free f) where
      wrap :: forall a. f (Free f a) -> Free f a
    wrap = f (Free f a) -> Free f a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free
      {-# INLINE wrap #-}

    -- |
    -- 'retract' is the left inverse of 'lift' and 'liftF'
    --
    -- @
    -- 'retract' . 'lift' = 'id'
    -- 'retract' . 'liftF' = 'id'
    -- @
    retract :: Monad f => Free f a -> f a
    retract :: forall (f :: * -> *) a. Monad f => Free f a -> f a
    retract = (forall x. f x -> f x) -> Free f a -> f a
    forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    (forall x. f x -> m x) -> Free f a -> m a
    foldFree f x -> f x
    forall a. a -> a
    forall x. f x -> f x
    id

    -- | Given an applicative homomorphism from @f@ to 'Identity', tear down a 'Free' 'Monad' using iteration.
    iter :: Applicative f => (f a -> a) -> Free f a -> a
    iter :: forall (f :: * -> *) a.
    Applicative f =>
    (f a -> a) -> Free f a -> a
    iter f a -> a
    _ (Pure a
    a) = a
    a
    iter f a -> a
    phi (Free f (Free f a)
    m) = f a -> a
    phi ((f a -> a) -> Free f a -> a
    forall (f :: * -> *) a.
    Applicative f =>
    (f a -> a) -> Free f a -> a
    iter f a -> a
    phi (Free f a -> a) -> f (Free f a) -> f a
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    m)

    -- | Like 'iter' for applicative values.
    iterA :: (Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a
    iterA :: forall (p :: * -> *) (f :: * -> *) a.
    (Applicative p, Applicative f) =>
    (f (p a) -> p a) -> Free f a -> p a
    iterA f (p a) -> p a
    _   (Pure a
    x) = a -> p a
    forall a. a -> p a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure a
    x
    iterA f (p a) -> p a
    phi (Free f (Free f a)
    f) = f (p a) -> p a
    phi ((f (p a) -> p a) -> Free f a -> p a
    forall (p :: * -> *) (f :: * -> *) a.
    (Applicative p, Applicative f) =>
    (f (p a) -> p a) -> Free f a -> p a
    iterA f (p a) -> p a
    phi (Free f a -> p a) -> f (Free f a) -> f (p a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    f)

    -- | Like 'iter' for monadic values.
    iterM :: (Monad m, Applicative f) => (f (m a) -> m a) -> Free f a -> m a
    iterM :: forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Applicative f) =>
    (f (m a) -> m a) -> Free f a -> m a
    iterM f (m a) -> m a
    _   (Pure a
    x) = a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x
    iterM f (m a) -> m a
    phi (Free f (Free f a)
    f) = f (m a) -> m a
    phi ((f (m a) -> m a) -> Free f a -> m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Applicative f) =>
    (f (m a) -> m a) -> Free f a -> m a
    iterM f (m a) -> m a
    phi (Free f a -> m a) -> f (Free f a) -> f (m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Free f a)
    f)

    -- | Lift an applicative homomorphism from @f@ to @g@ into a monad homomorphism from @'Free' f@ to @'Free' g@.
    hoistFree :: (Applicative f, Applicative g) => (forall a. f a -> g a) -> Free f b -> Free g b
    hoistFree :: forall (f :: * -> *) (g :: * -> *) b.
    (Applicative f, Applicative g) =>
    (forall a. f a -> g a) -> Free f b -> Free g b
    hoistFree forall a. f a -> g a
    f = (forall x. f x -> Free g x) -> Free f b -> Free g b
    forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    (forall x. f x -> m x) -> Free f a -> m a
    foldFree (g x -> Free g x
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, MonadFree f m) =>
    f a -> m a
    liftF (g x -> Free g x) -> (f x -> g x) -> f x -> Free g x
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f x -> g x
    forall a. f a -> g a
    f)

    -- | Given an applicative homomorphism, you get a monad homomorphism.
    foldFree :: (Applicative f, Monad m) => (forall x . f x -> m x) -> Free f a -> m a
    foldFree :: forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    (forall x. f x -> m x) -> Free f a -> m a
    foldFree forall x. f x -> m x
    _ (Pure a
    a)  = a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    a
    foldFree forall x. f x -> m x
    f (Free f (Free f a)
    as) = f (Free f a) -> m (Free f a)
    forall x. f x -> m x
    f f (Free f a)
    as m (Free f a) -> (Free f a -> m a) -> m a
    forall a b. m a -> (a -> m b) -> m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= (forall x. f x -> m x) -> Free f a -> m a
    forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    (forall x. f x -> m x) -> Free f a -> m a
    foldFree f x -> m x
    forall x. f x -> m x
    f

    -- | Convert a 'Free' monad from "Control.Monad.Free.Ap" to a 'FreeT.FreeT' monad
    -- from "Control.Monad.Trans.Free.Ap".
    -- WARNING: This assumes that 'liftF' is an applicative homomorphism.
    toFreeT :: (Applicative f, Monad m) => Free f a -> FreeT.FreeT f m a
    toFreeT :: forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    Free f a -> FreeT f m a
    toFreeT = (forall x. f x -> FreeT f m x) -> Free f a -> FreeT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (Applicative f, Monad m) =>
    (forall x. f x -> m x) -> Free f a -> m a
    foldFree f x -> FreeT f m x
    forall x. f x -> FreeT f m x
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, MonadFree f m) =>
    f a -> m a
    liftF

    -- | Cuts off a tree of computations at a given depth.
    -- If the depth is 0 or less, no computation nor
    -- monadic effects will take place.
    --
    -- Some examples (n ≥ 0):
    --
    -- prop> cutoff 0     _        == return Nothing
    -- prop> cutoff (n+1) . return == return . Just
    -- prop> cutoff (n+1) . lift   ==   lift . liftM Just
    -- prop> cutoff (n+1) . wrap   ==  wrap . fmap (cutoff n)
    --
    -- Calling 'retract . cutoff n' is always terminating, provided each of the
    -- steps in the iteration is terminating.
    cutoff :: (Applicative f) => Integer -> Free f a -> Free f (Maybe a)
    cutoff :: forall (f :: * -> *) a.
    Applicative f =>
    Integer -> Free f a -> Free f (Maybe a)
    cutoff Integer
    n Free f a
    _ | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Integer
    0 = Maybe a -> Free f (Maybe a)
    forall a. a -> Free f a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
    cutoff Integer
    n (Free f (Free f a)
    f) = f (Free f (Maybe a)) -> Free f (Maybe a)
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f (Maybe a)) -> Free f (Maybe a))
    -> f (Free f (Maybe a)) -> Free f (Maybe a)
    forall a b. (a -> b) -> a -> b
    $ (Free f a -> Free f (Maybe a))
    -> f (Free f a) -> f (Free f (Maybe a))
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Integer -> Free f a -> Free f (Maybe a)
    forall (f :: * -> *) a.
    Applicative f =>
    Integer -> Free f a -> Free f (Maybe a)
    cutoff (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    1)) f (Free f a)
    f
    cutoff Integer
    _ Free f a
    m = a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> Free f a -> Free f (Maybe a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Free f a
    m

    -- | Unfold a free monad from a seed.
    unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a
    unfold :: forall (f :: * -> *) b a.
    Applicative f =>
    (b -> Either a (f b)) -> b -> Free f a
    unfold b -> Either a (f b)
    f = b -> Either a (f b)
    f (b -> Either a (f b))
    -> (Either a (f b) -> Free f a) -> b -> Free f a
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> (a -> Free f a) -> (f b -> Free f a) -> Either a (f b) -> Free f a
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either a -> Free f a
    forall (f :: * -> *) a. a -> Free f a
    Pure (f (Free f a) -> Free f a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (f (Free f a) -> Free f a)
    -> (f b -> f (Free f a)) -> f b -> Free f a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> Free f a) -> f b -> f (Free f a)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((b -> Either a (f b)) -> b -> Free f a
    forall (f :: * -> *) b a.
    Applicative f =>
    (b -> Either a (f b)) -> b -> Free f a
    unfold b -> Either a (f b)
    f))

    -- | Unfold a free monad from a seed, monadically.
    unfoldM :: (Applicative f, Traversable f, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a)
    unfoldM :: forall (f :: * -> *) (m :: * -> *) b a.
    (Applicative f, Traversable f, Monad m) =>
    (b -> m (Either a (f b))) -> b -> m (Free f a)
    unfoldM b -> m (Either a (f b))
    f = b -> m (Either a (f b))
    f (b -> m (Either a (f b)))
    -> (Either a (f b) -> m (Free f a)) -> b -> m (Free f a)
    forall (m :: * -> *) a b c.
    Monad m =>
    (a -> m b) -> (b -> m c) -> a -> m c
    >=> (a -> m (Free f a))
    -> (f b -> m (Free f a)) -> Either a (f b) -> m (Free f a)
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either (Free f a -> m (Free f a)
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Free f a -> m (Free f a)) -> (a -> Free f a) -> a -> m (Free f a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Free f a
    forall a. a -> Free f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure) ((f (Free f a) -> Free f a) -> m (f (Free f a)) -> m (Free f a)
    forall a b. (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap f (Free f a) -> Free f a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free (m (f (Free f a)) -> m (Free f a))
    -> (f b -> m (f (Free f a))) -> f b -> m (Free f a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> m (Free f a)) -> f b -> m (f (Free f a))
    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 ((b -> m (Either a (f b))) -> b -> m (Free f a)
    forall (f :: * -> *) (m :: * -> *) b a.
    (Applicative f, Traversable f, Monad m) =>
    (b -> m (Either a (f b))) -> b -> m (Free f a)
    unfoldM b -> m (Either a (f b))
    f))

    -- | This is @Prism' (Free f a) a@ in disguise
    --
    -- >>> preview _Pure (Pure 3)
    -- Just 3
    --
    -- >>> review _Pure 3 :: Free Maybe Int
    -- Pure 3
    _Pure :: forall f m a p. (Choice p, Applicative m)
          => p a (m a) -> p (Free f a) (m (Free f a))
    _Pure :: forall (f :: * -> *) (m :: * -> *) a (p :: * -> * -> *).
    (Choice p, Applicative m) =>
    p a (m a) -> p (Free f a) (m (Free f a))
    _Pure = (Free f a -> Either (Free f a) a)
    -> (Either (Free f a) (m a) -> m (Free f a))
    -> p (Either (Free f a) a) (Either (Free f a) (m a))
    -> p (Free f a) (m (Free f a))
    forall a b c d. (a -> b) -> (c -> d) -> p b c -> p a d
    forall (p :: * -> * -> *) a b c d.
    Profunctor p =>
    (a -> b) -> (c -> d) -> p b c -> p a d
    dimap Free f a -> Either (Free f a) a
    forall {f :: * -> *} {b}. Free f b -> Either (Free f b) b
    impure ((Free f a -> m (Free f a))
    -> (m a -> m (Free f a)) -> Either (Free f a) (m a) -> m (Free f a)
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either Free f a -> m (Free f a)
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ((a -> Free f a) -> m a -> m (Free f a)
    forall a b. (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Free f a
    forall (f :: * -> *) a. a -> Free f a
    Pure)) (p (Either (Free f a) a) (Either (Free f a) (m a))
     -> p (Free f a) (m (Free f a)))
    -> (p a (m a) -> p (Either (Free f a) a) (Either (Free f a) (m a)))
    -> p a (m a)
    -> p (Free f a) (m (Free f a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . p a (m a) -> p (Either (Free f a) a) (Either (Free f a) (m a))
    forall a b c. p a b -> p (Either c a) (Either c b)
    forall (p :: * -> * -> *) a b c.
    Choice p =>
    p a b -> p (Either c a) (Either c b)
    right'
     where
      impure :: Free f b -> Either (Free f b) b
    impure (Pure b
    x) = b -> Either (Free f b) b
    forall a b. b -> Either a b
    Right b
    x
      impure Free f b
    x        = Free f b -> Either (Free f b) b
    forall a b. a -> Either a b
    Left Free f b
    x
      {-# INLINE impure #-}
    {-# INLINE _Pure #-}

    -- | This is @Prism' (Free f a) (f (Free f a))@ in disguise
    --
    -- >>> preview _Free (review _Free (Just (Pure 3)))
    -- Just (Just (Pure 3))
    --
    -- >>> review _Free (Just (Pure 3))
    -- Free (Just (Pure 3))
    _Free :: forall f m a p. (Choice p, Applicative m)
          => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
    _Free :: forall (f :: * -> *) (m :: * -> *) a (p :: * -> * -> *).
    (Choice p, Applicative m) =>
    p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
    _Free = (Free f a -> Either (Free f a) (f (Free f a)))
    -> (Either (Free f a) (m (f (Free f a))) -> m (Free f a))
    -> p (Either (Free f a) (f (Free f a)))
         (Either (Free f a) (m (f (Free f a))))
    -> p (Free f a) (m (Free f a))
    forall a b c d. (a -> b) -> (c -> d) -> p b c -> p a d
    forall (p :: * -> * -> *) a b c d.
    Profunctor p =>
    (a -> b) -> (c -> d) -> p b c -> p a d
    dimap Free f a -> Either (Free f a) (f (Free f a))
    forall {f :: * -> *} {a}.
    Free f a -> Either (Free f a) (f (Free f a))
    unfree ((Free f a -> m (Free f a))
    -> (m (f (Free f a)) -> m (Free f a))
    -> Either (Free f a) (m (f (Free f a)))
    -> m (Free f a)
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either Free f a -> m (Free f a)
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ((f (Free f a) -> Free f a) -> m (f (Free f a)) -> m (Free f a)
    forall a b. (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap f (Free f a) -> Free f a
    forall (f :: * -> *) a. f (Free f a) -> Free f a
    Free)) (p (Either (Free f a) (f (Free f a)))
       (Either (Free f a) (m (f (Free f a))))
     -> p (Free f a) (m (Free f a)))
    -> (p (f (Free f a)) (m (f (Free f a)))
        -> p (Either (Free f a) (f (Free f a)))
             (Either (Free f a) (m (f (Free f a)))))
    -> p (f (Free f a)) (m (f (Free f a)))
    -> p (Free f a) (m (Free f a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . p (f (Free f a)) (m (f (Free f a)))
    -> p (Either (Free f a) (f (Free f a)))
         (Either (Free f a) (m (f (Free f a))))
    forall a b c. p a b -> p (Either c a) (Either c b)
    forall (p :: * -> * -> *) a b c.
    Choice p =>
    p a b -> p (Either c a) (Either c b)
    right'
     where
      unfree :: Free f a -> Either (Free f a) (f (Free f a))
    unfree (Free f (Free f a)
    x) = f (Free f a) -> Either (Free f a) (f (Free f a))
    forall a b. b -> Either a b
    Right f (Free f a)
    x
      unfree Free f a
    x        = Free f a -> Either (Free f a) (f (Free f a))
    forall a b. a -> Either a b
    Left Free f a
    x
      {-# INLINE unfree #-}
    {-# INLINE _Free #-}