    {-# LANGUAGE CPP #-}
    {-# LANGUAGE FlexibleInstances #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE RankNTypes #-}
    {-# LANGUAGE UndecidableInstances #-}
    #include "free-common.h"

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Control.Monad.Trans.Free.Church
    -- Copyright   :  (C) 2008-2014 Edward Kmett
    -- License     :  BSD-style (see the file LICENSE)
    --
    -- Maintainer  :  Edward Kmett <ekmett@gmail.com>
    -- Stability   :  provisional
    -- Portability :  non-portable (rank-2 polymorphism, MTPCs)
    --
    -- Church-encoded free monad transformer.
    --
    -----------------------------------------------------------------------------
    module Control.Monad.Trans.Free.Church
      (
      -- * The free monad transformer
        FT(..)
      -- * The free monad
      , F, free, runF
      -- * Operations
      , improveT
      , toFT, fromFT
      , iterT
      , iterTM
      , hoistFT
      , transFT
      , joinFT
      , cutoff
      -- * Operations of free monad
      , improve
      , fromF, toF
      , retract
      , retractT
      , iter
      , iterM
      -- * Free Monads With Class
      , MonadFree(..)
      , liftF
      ) where

    import Control.Applicative
    import Control.Category ((<<<), (>>>))
    import Control.Monad
    import Control.Monad.Catch (MonadCatch(..), MonadThrow(..))
    import Control.Monad.Identity
    import Control.Monad.Trans.Class
    import Control.Monad.IO.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 Control.Monad.Free.Class
    import Control.Monad.Trans.Free (FreeT(..), FreeF(..), Free)
    import qualified Control.Monad.Trans.Free as FreeT
    import qualified Data.Foldable as F
    import qualified Data.Traversable as T
    import Data.Functor.Bind hiding (join)
    import Data.Functor.Classes.Compat

    #if !(MIN_VERSION_base(4,8,0))
    import Data.Foldable (Foldable)
    import Data.Traversable (Traversable)
    #endif

    -- | The \"free monad transformer\" for a functor @f@
    newtype FT f m a = FT { FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r }

    #ifdef LIFTED_FUNCTOR_CLASSES
    instance (Functor f, Monad m, Eq1 f, Eq1 m) => Eq1 (FT f m) where
      liftEq :: (a -> b -> Bool) -> FT f m a -> FT f m b -> Bool
    liftEq eq :: a -> b -> Bool
    eq x :: FT f m a
    x y :: FT f m b
    y = (a -> b -> Bool) -> FreeT f m a -> FreeT f m b -> Bool
    forall (f :: * -> *) a b.
    Eq1 f =>
    (a -> b -> Bool) -> f a -> f b -> Bool
    liftEq a -> b -> Bool
    eq (FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m a
    x) (FT f m b -> FreeT f m b
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m b
    y)

    instance (Functor f, Monad m, Ord1 f, Ord1 m) => Ord1 (FT f m) where
      liftCompare :: (a -> b -> Ordering) -> FT f m a -> FT f m b -> Ordering
    liftCompare cmp :: a -> b -> Ordering
    cmp x :: FT f m a
    x y :: FT f m b
    y= (a -> b -> Ordering) -> FreeT f m a -> FreeT f m b -> Ordering
    forall (f :: * -> *) a b.
    Ord1 f =>
    (a -> b -> Ordering) -> f a -> f b -> Ordering
    liftCompare a -> b -> Ordering
    cmp (FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m a
    x) (FT f m b -> FreeT f m b
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m b
    y)
    #else
    instance ( Functor f, Monad m, Eq1 f, Eq1 m
    # if !(MIN_VERSION_base(4,8,0))
             , Functor m
    # endif
             ) => Eq1 (FT f m) where
      eq1 x y = eq1 (fromFT x) (fromFT y)

    instance ( Functor f, Monad m, Ord1 f, Ord1 m
    # if !(MIN_VERSION_base(4,8,0))
             , Functor m
    # endif
             ) => Ord1 (FT f m) where
      compare1 x y = compare1 (fromFT x) (fromFT y)
    #endif

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

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

    instance Functor (FT f m) where
      fmap :: (a -> b) -> FT f m a -> FT f m b
    fmap f :: a -> b
    f (FT k :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k) = (forall r.
     (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m b)
    -> (forall r.
        (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall a b. (a -> b) -> a -> b
    $ \a :: b -> m r
    a fr :: forall x. (x -> m r) -> f x -> m r
    fr -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k (b -> m r
    a (b -> m r) -> (a -> b) -> a -> m r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> b
    f) forall x. (x -> m r) -> f x -> m r
    fr

    instance Apply (FT f m) where
      <.> :: FT f m (a -> b) -> FT f m a -> FT f m b
    (<.>) = FT f m (a -> b) -> FT f m a -> FT f m b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    (<*>)

    instance Applicative (FT f m) where
      pure :: a -> FT f m a
    pure a :: a
    a = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m a)
    -> (forall r.
        (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ \k :: a -> m r
    k _ -> a -> m r
    k a
    a
      FT fk :: forall r.
    ((a -> b) -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    fk <*> :: FT f m (a -> b) -> FT f m a -> FT f m b
    <*> FT ak :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    ak = (forall r.
     (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m b)
    -> (forall r.
        (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall a b. (a -> b) -> a -> b
    $ \b :: b -> m r
    b fr :: forall x. (x -> m r) -> f x -> m r
    fr -> ((a -> b) -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r.
    ((a -> b) -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    fk (\e :: a -> b
    e -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    ak (\d :: a
    d -> b -> m r
    b (a -> b
    e a
    d)) forall x. (x -> m r) -> f x -> m r
    fr) forall x. (x -> m r) -> f x -> m r
    fr

    instance Bind (FT f m) where
      >>- :: FT f m a -> (a -> FT f m b) -> FT f m b
    (>>-) = FT f m a -> (a -> FT f m b) -> FT f m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    (>>=)

    instance Monad (FT f m) where
      return :: a -> FT f m a
    return = a -> FT f m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      FT fk :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    fk >>= :: FT f m a -> (a -> FT f m b) -> FT f m b
    >>= f :: a -> FT f m b
    f = (forall r.
     (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m b)
    -> (forall r.
        (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m b
    forall a b. (a -> b) -> a -> b
    $ \b :: b -> m r
    b fr :: forall x. (x -> m r) -> f x -> m r
    fr -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    fk (\d :: a
    d -> FT f m b
    -> (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall (f :: * -> *) (m :: * -> *) a.
    FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT (a -> FT f m b
    f a
    d) b -> m r
    b forall x. (x -> m r) -> f x -> m r
    fr) forall x. (x -> m r) -> f x -> m r
    fr

    instance MonadFree f (FT f m) where
      wrap :: f (FT f m a) -> FT f m a
    wrap f :: f (FT f m a)
    f = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\kp :: a -> m r
    kp kf :: forall x. (x -> m r) -> f x -> m r
    kf -> (FT f m a -> m r) -> f (FT f m a) -> m r
    forall x. (x -> m r) -> f x -> m r
    kf (\ft :: FT f m a
    ft -> FT f m a
    -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall (f :: * -> *) (m :: * -> *) a.
    FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT FT f m a
    ft a -> m r
    kp forall x. (x -> m r) -> f x -> m r
    kf) f (FT f m a)
    f)

    instance MonadTrans (FT f) where
      lift :: m a -> FT f m a
    lift m :: m a
    m = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\a :: a -> m r
    a _ -> m a
    m m a -> (a -> m r) -> m r
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= a -> m r
    a)

    instance Alternative m => Alternative (FT f m) where
      empty :: FT f m a
    empty = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\_ _ -> m r
    forall (f :: * -> *) a. Alternative f => f a
    empty)
      FT k1 :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k1 <|> :: FT f m a -> FT f m a -> FT f m a
    <|> FT k2 :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k2 = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m a)
    -> (forall r.
        (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ \a :: a -> m r
    a fr :: forall x. (x -> m r) -> f x -> m r
    fr -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k1 a -> m r
    a forall x. (x -> m r) -> f x -> m r
    fr m r -> m r -> m r
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k2 a -> m r
    a forall x. (x -> m r) -> f x -> m r
    fr

    instance MonadPlus m => MonadPlus (FT f m) where
      mzero :: FT f m a
    mzero = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\_ _ -> m r
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
      mplus :: FT f m a -> FT f m a -> FT f m a
    mplus (FT k1 :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k1) (FT k2 :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k2) = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m a)
    -> (forall r.
        (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ \a :: a -> m r
    a fr :: forall x. (x -> m r) -> f x -> m r
    fr -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k1 a -> m r
    a forall x. (x -> m r) -> f x -> m r
    fr m r -> m r -> m r
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k2 a -> m r
    a forall x. (x -> m r) -> f x -> m r
    fr

    instance (Foldable f, Foldable m, Monad m) => Foldable (FT f m) where
      foldr :: (a -> b -> b) -> b -> FT f m a -> b
    foldr f :: a -> b -> b
    f r :: b
    r xs :: FT f m a
    xs = ((b -> b) -> (b -> b) -> b -> b)
    -> (b -> b) -> m (b -> b) -> b -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    F.foldr (b -> b) -> (b -> b) -> b -> b
    forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    (<<<) b -> b
    forall a. a -> a
    id m (b -> b)
    inner b
    r
        where
          inner :: m (b -> b)
    inner = FT f m a
    -> (a -> m (b -> b))
    -> (forall x. (x -> m (b -> b)) -> f x -> m (b -> b))
    -> m (b -> b)
    forall (f :: * -> *) (m :: * -> *) a.
    FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT FT f m a
    xs ((b -> b) -> m (b -> b)
    forall (m :: * -> *) a. Monad m => a -> m a
    return ((b -> b) -> m (b -> b)) -> (a -> b -> b) -> a -> m (b -> b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> b -> b
    f) (\xg :: x -> m (b -> b)
    xg xf :: f x
    xf -> (x -> m (b -> b) -> m (b -> b)) -> m (b -> b) -> f x -> m (b -> b)
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    F.foldr (((b -> b) -> (b -> b) -> b -> b)
    -> m (b -> b) -> m (b -> b) -> m (b -> b)
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 (b -> b) -> (b -> b) -> b -> b
    forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    (<<<) (m (b -> b) -> m (b -> b) -> m (b -> b))
    -> (x -> m (b -> b)) -> x -> m (b -> b) -> m (b -> b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (b -> b)
    xg) ((b -> b) -> m (b -> b)
    forall (m :: * -> *) a. Monad m => a -> m a
    return b -> b
    forall a. a -> a
    id) f x
    xf)
      {-# INLINE foldr #-}

    #if MIN_VERSION_base(4,6,0)
      foldl' :: (b -> a -> b) -> b -> FT f m a -> b
    foldl' f :: b -> a -> b
    f z :: b
    z xs :: FT f m a
    xs = ((b -> b) -> (b -> b) -> b -> b)
    -> (b -> b) -> m (b -> b) -> b -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    F.foldl' (b -> b) -> (b -> b) -> b -> b
    forall t a b. (t -> a) -> (a -> b) -> t -> b
    (!>>>) b -> b
    forall a. a -> a
    id m (b -> b)
    inner b
    z
        where
          !>>> :: (t -> a) -> (a -> b) -> t -> b
    (!>>>) h :: t -> a
    h g :: a -> b
    g = \r :: t
    r -> a -> b
    g (a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $! t -> a
    h t
    r
          inner :: m (b -> b)
    inner = FT f m a
    -> (a -> m (b -> b))
    -> (forall x. (x -> m (b -> b)) -> f x -> m (b -> b))
    -> m (b -> b)
    forall (f :: * -> *) (m :: * -> *) a.
    FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT FT f m a
    xs ((b -> b) -> m (b -> b)
    forall (m :: * -> *) a. Monad m => a -> m a
    return ((b -> b) -> m (b -> b)) -> (a -> b -> b) -> a -> m (b -> b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> a -> b) -> a -> b -> b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip b -> a -> b
    f) (\xg :: x -> m (b -> b)
    xg xf :: f x
    xf -> (x -> m (b -> b) -> m (b -> b)) -> m (b -> b) -> f x -> m (b -> b)
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    F.foldr (((b -> b) -> (b -> b) -> b -> b)
    -> m (b -> b) -> m (b -> b) -> m (b -> b)
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 (b -> b) -> (b -> b) -> b -> b
    forall k (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    (>>>) (m (b -> b) -> m (b -> b) -> m (b -> b))
    -> (x -> m (b -> b)) -> x -> m (b -> b) -> m (b -> b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (b -> b)
    xg) ((b -> b) -> m (b -> b)
    forall (m :: * -> *) a. Monad m => a -> m a
    return b -> b
    forall a. a -> a
    id) f x
    xf)
      {-# INLINE foldl' #-}
    #endif

    instance (Monad m, Traversable m, Traversable f) => Traversable (FT f m) where
      traverse :: (a -> f b) -> FT f m a -> f (FT f m b)
    traverse f :: a -> f b
    f (FT k :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k) = (m (FT f m b) -> FT f m b) -> f (m (FT f m b)) -> f (FT f m b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (FT f m (FT f m b) -> FT f m b
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (FT f m (FT f m b) -> FT f m b)
    -> (m (FT f m b) -> FT f m (FT f m b)) -> m (FT f m b) -> FT f m b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (FT f m b) -> FT f m (FT f m b)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift) (f (m (FT f m b)) -> f (FT f m b))
    -> (m (f (FT f m b)) -> f (m (FT f m b)))
    -> m (f (FT f m b))
    -> f (FT f m b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (f (FT f m b)) -> f (m (FT f m b))
    forall (t :: * -> *) (f :: * -> *) a.
    (Traversable t, Applicative f) =>
    t (f a) -> f (t a)
    T.sequenceA (m (f (FT f m b)) -> f (FT f m b))
    -> m (f (FT f m b)) -> f (FT f m b)
    forall a b. (a -> b) -> a -> b
    $ (a -> m (f (FT f m b)))
    -> (forall x. (x -> m (f (FT f m b))) -> f x -> m (f (FT f m b)))
    -> m (f (FT f m b))
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k a -> m (f (FT f m b))
    traversePure forall x. (x -> m (f (FT f m b))) -> f x -> m (f (FT f m b))
    forall (f :: * -> *) (t :: (* -> *) -> * -> *) (m :: * -> *)
           (m :: * -> *) (f :: * -> *) a a.
    (MonadFree f (t m), MonadTrans t, Monad m, Monad m, Traversable f,
     Traversable m, Applicative f) =>
    (a -> m (f (t m a))) -> f a -> m (f (t m a))
    traverseFree
        where
          traversePure :: a -> m (f (FT f m b))
    traversePure = f (FT f m b) -> m (f (FT f m b))
    forall (m :: * -> *) a. Monad m => a -> m a
    return (f (FT f m b) -> m (f (FT f m b)))
    -> (a -> f (FT f m b)) -> a -> m (f (FT f m b))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> FT f m b) -> f b -> f (FT f m b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap b -> FT f m b
    forall (m :: * -> *) a. Monad m => a -> m a
    return (f b -> f (FT f m b)) -> (a -> f b) -> a -> f (FT f m b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> f b
    f
          traverseFree :: (a -> m (f (t m a))) -> f a -> m (f (t m a))
    traverseFree xg :: a -> m (f (t m a))
    xg = f (t m a) -> m (f (t m a))
    forall (m :: * -> *) a. Monad m => a -> m a
    return (f (t m a) -> m (f (t m a)))
    -> (f a -> f (t m a)) -> f a -> m (f (t m a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (f (m (t m a)) -> t m a) -> f (f (m (t m a))) -> f (t m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (f (t m a) -> t m a
    forall (f :: * -> *) (m :: * -> *) a.
    MonadFree f m =>
    f (m a) -> m a
    wrap (f (t m a) -> t m a)
    -> (f (m (t m a)) -> f (t m a)) -> f (m (t m a)) -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (m (t m a) -> t m a) -> f (m (t m a)) -> f (t m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (t m (t m a) -> t m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (t m (t m a) -> t m a)
    -> (m (t m a) -> t m (t m a)) -> m (t m a) -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (t m a) -> t m (t m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift)) (f (f (m (t m a))) -> f (t m a))
    -> (f a -> f (f (m (t m a)))) -> f a -> f (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> f (m (t m a))) -> f a -> f (f (m (t m a)))
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    T.traverse (m (f (t m a)) -> f (m (t m a))
    forall (t :: * -> *) (f :: * -> *) a.
    (Traversable t, Applicative f) =>
    t (f a) -> f (t a)
    T.sequenceA (m (f (t m a)) -> f (m (t m a)))
    -> (a -> m (f (t m a))) -> a -> f (m (t m a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> m (f (t m a))
    xg)

    instance (MonadIO m) => MonadIO (FT f m) where
      liftIO :: IO a -> FT f m a
    liftIO = m a -> FT f m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> FT f m a) -> (IO a -> m a) -> IO a -> FT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IO a -> m a
    forall (m :: * -> *) a. MonadIO m => IO a -> m a
    liftIO
      {-# INLINE liftIO #-}

    instance (Functor f, MonadError e m) => MonadError e (FT f m) where
      throwError :: e -> FT f m a
    throwError = m a -> FT f m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> FT f m a) -> (e -> m a) -> e -> FT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> m a
    forall e (m :: * -> *) a. MonadError e m => e -> m a
    throwError
      {-# INLINE throwError #-}
      m :: FT f m a
    m catchError :: FT f m a -> (e -> FT f m a) -> FT f m a
    `catchError` f :: e -> FT f m a
    f = FreeT f m a -> FT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT (FreeT f m a -> FT f m a) -> FreeT f m a -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m a
    m FreeT f m a -> (e -> FreeT f m a) -> FreeT f m a
    forall e (m :: * -> *) a.
    MonadError e m =>
    m a -> (e -> m a) -> m a
    `catchError` (FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT (FT f m a -> FreeT f m a) -> (e -> FT f m a) -> e -> FreeT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> FT f m a
    f)

    instance MonadCont m => MonadCont (FT f m) where
      callCC :: ((a -> FT f m b) -> FT f m a) -> FT f m a
    callCC f :: (a -> FT f m b) -> FT f m a
    f = FT f m (FT f m a) -> FT f m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (FT f m (FT f m a) -> FT f m a)
    -> (m (FT f m a) -> FT f m (FT f m a)) -> m (FT f m a) -> FT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (FT f m a) -> FT f m (FT f m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (FT f m a) -> FT f m a) -> m (FT f m a) -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ ((FT f m a -> m b) -> m (FT f m a)) -> m (FT f m a)
    forall (m :: * -> *) a b. MonadCont m => ((a -> m b) -> m a) -> m a
    callCC (\k :: FT f m a -> m b
    k -> FT f m a -> m (FT f m a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (FT f m a -> m (FT f m a)) -> FT f m a -> m (FT f m a)
    forall a b. (a -> b) -> a -> b
    $ (a -> FT f m b) -> FT f m a
    f (m b -> FT f m b
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m b -> FT f m b) -> (a -> m b) -> a -> FT f m b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FT f m a -> m b
    k (FT f m a -> m b) -> (a -> FT f m a) -> a -> m b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> FT f m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return))

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

    instance (Functor f, MonadWriter w m) => MonadWriter w (FT f m) where
      tell :: w -> FT f m ()
    tell = m () -> FT f m ()
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m () -> FT f m ()) -> (w -> m ()) -> w -> FT f m ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . w -> m ()
    forall w (m :: * -> *). MonadWriter w m => w -> m ()
    tell
      {-# INLINE tell #-}
      listen :: FT f m a -> FT f m (a, w)
    listen = FreeT f m (a, w) -> FT f m (a, w)
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT (FreeT f m (a, w) -> FT f m (a, w))
    -> (FT f m a -> FreeT f m (a, w)) -> FT f m a -> FT f m (a, w)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FreeT f m a -> FreeT f m (a, w)
    forall w (m :: * -> *) a. MonadWriter w m => m a -> m (a, w)
    listen (FreeT f m a -> FreeT f m (a, w))
    -> (FT f m a -> FreeT f m a) -> FT f m a -> FreeT f m (a, w)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT
      pass :: FT f m (a, w -> w) -> FT f m a
    pass = FreeT f m a -> FT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT (FreeT f m a -> FT f m a)
    -> (FT f m (a, w -> w) -> FreeT f m a)
    -> FT f m (a, w -> w)
    -> FT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FreeT f m (a, w -> w) -> FreeT f m a
    forall w (m :: * -> *) a. MonadWriter w m => m (a, w -> w) -> m a
    pass (FreeT f m (a, w -> w) -> FreeT f m a)
    -> (FT f m (a, w -> w) -> FreeT f m (a, w -> w))
    -> FT f m (a, w -> w)
    -> FreeT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FT f m (a, w -> w) -> FreeT f m (a, w -> w)
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT
    #if MIN_VERSION_mtl(2,1,1)
      writer :: (a, w) -> FT f m a
    writer w :: (a, w)
    w = m a -> FT f m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift ((a, w) -> m a
    forall w (m :: * -> *) a. MonadWriter w m => (a, w) -> m a
    writer (a, w)
    w)
      {-# INLINE writer #-}
    #endif

    instance MonadState s m => MonadState s (FT f m) where
      get :: FT f m s
    get = m s -> FT f m s
    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 -> FT f m ()
    put = m () -> FT f m ()
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m () -> FT f m ()) -> (s -> m ()) -> s -> FT f m ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . s -> m ()
    forall s (m :: * -> *). MonadState s m => s -> m ()
    put
      {-# INLINE put #-}
    #if MIN_VERSION_mtl(2,1,1)
      state :: (s -> (a, s)) -> FT f m a
    state f :: s -> (a, s)
    f = m a -> FT f m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift ((s -> (a, s)) -> m a
    forall s (m :: * -> *) a. MonadState s m => (s -> (a, s)) -> m a
    state s -> (a, s)
    f)
      {-# INLINE state #-}
    #endif

    instance MonadThrow m => MonadThrow (FT f m) where
      throwM :: e -> FT f m a
    throwM = m a -> FT f m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> FT f m a) -> (e -> m a) -> e -> FT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> m a
    forall (m :: * -> *) e a. (MonadThrow m, Exception e) => e -> m a
    throwM
      {-# INLINE throwM #-}

    instance (Functor f, MonadCatch m) => MonadCatch (FT f m) where
      catch :: FT f m a -> (e -> FT f m a) -> FT f m a
    catch m :: FT f m a
    m f :: e -> FT f m a
    f = FreeT f m a -> FT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT (FreeT f m a -> FT f m a) -> FreeT f m a -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m a
    m FreeT f m a -> (e -> FreeT f m a) -> FreeT f m a
    forall (m :: * -> *) e a.
    (MonadCatch m, Exception e) =>
    m a -> (e -> m a) -> m a
    `Control.Monad.Catch.catch` (FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT (FT f m a -> FreeT f m a) -> (e -> FT f m a) -> e -> FreeT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> FT f m a
    f)
      {-# INLINE catch #-}

    -- | Generate a Church-encoded free monad transformer from a 'FreeT' monad
    -- transformer.
    toFT :: Monad m => FreeT f m a -> FT f m a
    toFT :: FreeT f m a -> FT f m a
    toFT (FreeT f :: m (FreeF f a (FreeT f m a))
    f) = (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT ((forall r.
      (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
     -> FT f m a)
    -> (forall r.
        (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    forall a b. (a -> b) -> a -> b
    $ \ka :: a -> m r
    ka kfr :: forall x. (x -> m r) -> f x -> m r
    kfr -> do
      FreeF f a (FreeT f m a)
    freef <- m (FreeF f a (FreeT f m a))
    f
      case FreeF f a (FreeT f m a)
    freef of
        Pure a :: a
    a -> a -> m r
    ka a
    a
        Free fb :: f (FreeT f m a)
    fb -> (FreeT f m a -> m r) -> f (FreeT f m a) -> m r
    forall x. (x -> m r) -> f x -> m r
    kfr (\x :: FreeT f m a
    x -> FT f m a
    -> (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall (f :: * -> *) (m :: * -> *) a.
    FT f m a
    -> forall r.
       (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    runFT (FreeT f m a -> FT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT FreeT f m a
    x) a -> m r
    ka forall x. (x -> m r) -> f x -> m r
    kfr) f (FreeT f m a)
    fb

    -- | Convert to a 'FreeT' free monad representation.
    fromFT :: (Monad m, Functor f) => FT f m a -> FreeT f m a
    fromFT :: FT f m a -> FreeT f m a
    fromFT (FT k :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k) = m (FreeF f a (FreeT f m a)) -> FreeT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    m (FreeF f a (FreeT f m a)) -> FreeT f m a
    FreeT (m (FreeF f a (FreeT f m a)) -> FreeT f m a)
    -> m (FreeF f a (FreeT f m a)) -> FreeT f m a
    forall a b. (a -> b) -> a -> b
    $ (a -> m (FreeF f a (FreeT f m a)))
    -> (forall x.
        (x -> m (FreeF f a (FreeT f m a)))
        -> f x -> m (FreeF f a (FreeT f m a)))
    -> m (FreeF f a (FreeT f m a))
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    k (FreeF f a (FreeT f m a) -> m (FreeF f a (FreeT f m a))
    forall (m :: * -> *) a. Monad m => a -> m a
    return (FreeF f a (FreeT f m a) -> m (FreeF f a (FreeT f m a)))
    -> (a -> FreeF f a (FreeT f m a))
    -> a
    -> m (FreeF f a (FreeT f m a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> FreeF f a (FreeT f m a)
    forall (f :: * -> *) a b. a -> FreeF f a b
    Pure) (\xg :: x -> m (FreeF f a (FreeT f m a))
    xg -> FreeT f m a -> m (FreeF f a (FreeT f m a))
    forall (f :: * -> *) (m :: * -> *) a.
    FreeT f m a -> m (FreeF f a (FreeT f m a))
    runFreeT (FreeT f m a -> m (FreeF f a (FreeT f m a)))
    -> (f x -> FreeT f m a) -> f x -> m (FreeF f a (FreeT f m a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f (FreeT f m a) -> FreeT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    MonadFree f m =>
    f (m a) -> m a
    wrap (f (FreeT f m a) -> FreeT f m a)
    -> (f x -> f (FreeT f m a)) -> f x -> FreeT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> FreeT f m a) -> f x -> f (FreeT f m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (m (FreeF f a (FreeT f m a)) -> FreeT f m a
    forall (f :: * -> *) (m :: * -> *) a.
    m (FreeF f a (FreeT f m a)) -> FreeT f m a
    FreeT (m (FreeF f a (FreeT f m a)) -> FreeT f m a)
    -> (x -> m (FreeF f a (FreeT f m a))) -> x -> FreeT f m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (FreeF f a (FreeT f m a))
    xg))

    -- | The \"free monad\" for a functor @f@.
    type F f = FT f Identity

    -- | Unwrap the 'Free' monad to obtain it's Church-encoded representation.
    runF :: Functor f => F f a -> (forall r. (a -> r) -> (f r -> r) -> r)
    runF :: F f a -> forall r. (a -> r) -> (f r -> r) -> r
    runF (FT m :: forall r.
    (a -> Identity r)
    -> (forall x. (x -> Identity r) -> f x -> Identity r) -> Identity r
    m) = \kp :: a -> r
    kp kf :: f r -> r
    kf -> Identity r -> r
    forall a. Identity a -> a
    runIdentity (Identity r -> r) -> Identity r -> r
    forall a b. (a -> b) -> a -> b
    $ (a -> Identity r)
    -> (forall x. (x -> Identity r) -> f x -> Identity r) -> Identity r
    forall r.
    (a -> Identity r)
    -> (forall x. (x -> Identity r) -> f x -> Identity r) -> Identity r
    m (r -> Identity r
    forall (m :: * -> *) a. Monad m => a -> m a
    return (r -> Identity r) -> (a -> r) -> a -> Identity r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> r
    kp) (\xg :: x -> Identity r
    xg -> r -> Identity r
    forall (m :: * -> *) a. Monad m => a -> m a
    return (r -> Identity r) -> (f x -> r) -> f x -> Identity r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f r -> r
    kf (f r -> r) -> (f x -> f r) -> f x -> r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> r) -> f x -> f r
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Identity r -> r
    forall a. Identity a -> a
    runIdentity (Identity r -> r) -> (x -> Identity r) -> x -> r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> Identity r
    xg))

    -- | Wrap a Church-encoding of a \"free monad\" as the free monad for a functor.
    free :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a
    free :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a
    free f :: forall r. (a -> r) -> (f r -> r) -> r
    f = (forall r.
     (a -> Identity r)
     -> (forall x. (x -> Identity r) -> f x -> Identity r)
     -> Identity r)
    -> F f a
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\kp :: a -> Identity r
    kp kf :: forall x. (x -> Identity r) -> f x -> Identity r
    kf -> r -> Identity r
    forall (m :: * -> *) a. Monad m => a -> m a
    return (r -> Identity r) -> r -> Identity r
    forall a b. (a -> b) -> a -> b
    $ (a -> r) -> (f r -> r) -> r
    forall r. (a -> r) -> (f r -> r) -> r
    f (Identity r -> r
    forall a. Identity a -> a
    runIdentity (Identity r -> r) -> (a -> Identity r) -> a -> r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Identity r
    kp) (Identity r -> r
    forall a. Identity a -> a
    runIdentity (Identity r -> r) -> (f r -> Identity r) -> f r -> r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (r -> Identity r) -> f r -> Identity r
    forall x. (x -> Identity r) -> f x -> Identity r
    kf r -> Identity r
    forall (m :: * -> *) a. Monad m => a -> m a
    return))

    -- | Tear down a free monad transformer using iteration.
    iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FT f m a -> m a
    iterT :: (f (m a) -> m a) -> FT f m a -> m a
    iterT phi :: f (m a) -> m a
    phi (FT m :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m) = (a -> m a) -> (forall x. (x -> m a) -> f x -> m a) -> m a
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (\xg :: x -> m a
    xg -> f (m a) -> m a
    phi (f (m a) -> m a) -> (f x -> f (m a)) -> f x -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> m a) -> f x -> f (m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap x -> m a
    xg)
    {-# INLINE iterT #-}

    -- | Tear down a free monad transformer using iteration over a transformer.
    iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FT f m a -> t m a
    iterTM :: (f (t m a) -> t m a) -> FT f m a -> t m a
    iterTM f :: f (t m a) -> t m a
    f (FT m :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m) = t m (t m a) -> t m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (t m (t m a) -> t m a)
    -> (m (t m a) -> t m (t m a)) -> m (t m a) -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (t m a) -> t m (t m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (t m a) -> t m a) -> m (t m a) -> t m a
    forall a b. (a -> b) -> a -> b
    $ (a -> m (t m a))
    -> (forall x. (x -> m (t m a)) -> f x -> m (t m a)) -> m (t m a)
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m (t m a -> m (t m a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (t m a -> m (t m a)) -> (a -> t m a) -> a -> m (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> t m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return) (\xg :: x -> m (t m a)
    xg -> t m a -> m (t m a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (t m a -> m (t m a)) -> (f x -> t m a) -> f x -> m (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f (t m a) -> t m a
    f (f (t m a) -> t m a) -> (f x -> f (t m a)) -> f x -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> t m a) -> f x -> f (t m a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (t m (t m a) -> t m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (t m (t m a) -> t m a) -> (x -> t m (t m a)) -> x -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (t m a) -> t m (t m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (t m a) -> t m (t m a)) -> (x -> m (t m a)) -> x -> t m (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (t m a)
    xg))

    -- | Lift a monad homomorphism from @m@ to @n@ into a monad homomorphism from @'FT' f m@ to @'FT' f n@
    --
    -- @'hoistFT' :: ('Monad' m, 'Monad' n, 'Functor' f) => (m ~> n) -> 'FT' f m ~> 'FT' f n@
    hoistFT :: (Monad m, Monad n) => (forall a. m a -> n a) -> FT f m b -> FT f n b
    hoistFT :: (forall a. m a -> n a) -> FT f m b -> FT f n b
    hoistFT phi :: forall a. m a -> n a
    phi (FT m :: forall r. (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m) = (forall r.
     (b -> n r) -> (forall x. (x -> n r) -> f x -> n r) -> n r)
    -> FT f n b
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\kp :: b -> n r
    kp kf :: forall x. (x -> n r) -> f x -> n r
    kf -> n (n r) -> n r
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (n (n r) -> n r) -> (m (n r) -> n (n r)) -> m (n r) -> n r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (n r) -> n (n r)
    forall a. m a -> n a
    phi (m (n r) -> n r) -> m (n r) -> n r
    forall a b. (a -> b) -> a -> b
    $ (b -> m (n r))
    -> (forall x. (x -> m (n r)) -> f x -> m (n r)) -> m (n r)
    forall r. (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m (n r -> m (n r)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (n r -> m (n r)) -> (b -> n r) -> b -> m (n r)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> n r
    kp) (\xg :: x -> m (n r)
    xg -> n r -> m (n r)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (n r -> m (n r)) -> (f x -> n r) -> f x -> m (n r)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> n r) -> f x -> n r
    forall x. (x -> n r) -> f x -> n r
    kf (n (n r) -> n r
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (n (n r) -> n r) -> (x -> n (n r)) -> x -> n r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (n r) -> n (n r)
    forall a. m a -> n a
    phi (m (n r) -> n (n r)) -> (x -> m (n r)) -> x -> n (n r)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (n r)
    xg)))

    -- | Lift a natural transformation from @f@ to @g@ into a monad homomorphism from @'FT' f m@ to @'FT' g n@
    transFT :: (forall a. f a -> g a) -> FT f m b -> FT g m b
    transFT :: (forall a. f a -> g a) -> FT f m b -> FT g m b
    transFT phi :: forall a. f a -> g a
    phi (FT m :: forall r. (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m) = (forall r.
     (b -> m r) -> (forall x. (x -> m r) -> g x -> m r) -> m r)
    -> FT g m b
    forall (f :: * -> *) (m :: * -> *) a.
    (forall r.
     (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r)
    -> FT f m a
    FT (\kp :: b -> m r
    kp kf :: forall x. (x -> m r) -> g x -> m r
    kf -> (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    forall r. (b -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m b -> m r
    kp (\xg :: x -> m r
    xg -> (x -> m r) -> g x -> m r
    forall x. (x -> m r) -> g x -> m r
    kf x -> m r
    xg (g x -> m r) -> (f x -> g x) -> f x -> m r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f x -> g x
    forall a. f a -> g a
    phi))

    -- | Pull out and join @m@ layers of @'FreeT' f m a@.
    joinFT :: (Monad m, Traversable f) => FT f m a -> m (F f a)
    joinFT :: FT f m a -> m (F f a)
    joinFT (FT m :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m) = (a -> m (F f a))
    -> (forall x. (x -> m (F f a)) -> f x -> m (F f a)) -> m (F f a)
    forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r
    m (F f a -> m (F f a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (F f a -> m (F f a)) -> (a -> F f a) -> a -> m (F f a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> F f a
    forall (m :: * -> *) a. Monad m => a -> m a
    return) (\xg :: x -> m (F f a)
    xg -> (f (F f a) -> F f a) -> m (f (F f a)) -> m (F f a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM f (F f a) -> F f a
    forall (f :: * -> *) (m :: * -> *) a.
    MonadFree f m =>
    f (m a) -> m a
    wrap (m (f (F f a)) -> m (F f a))
    -> (f x -> m (f (F f a))) -> f x -> m (F f a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (x -> m (F f a)) -> f x -> m (f (F f a))
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    T.mapM x -> m (F f a)
    xg)

    -- | 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 :: (Functor f, Monad m) => Integer -> FT f m a -> FT f m (Maybe a)
    cutoff :: Integer -> FT f m a -> FT f m (Maybe a)
    cutoff n :: Integer
    n = FreeT f m (Maybe a) -> FT f m (Maybe a)
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT (FreeT f m (Maybe a) -> FT f m (Maybe a))
    -> (FT f m a -> FreeT f m (Maybe a))
    -> FT f m a
    -> FT f m (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Integer -> FreeT f m a -> FreeT f m (Maybe a)
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, Monad m) =>
    Integer -> FreeT f m a -> FreeT f m (Maybe a)
    FreeT.cutoff Integer
    n (FreeT f m a -> FreeT f m (Maybe a))
    -> (FT f m a -> FreeT f m a) -> FT f m a -> FreeT f m (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT

    -- |
    -- 'retract' is the left inverse of 'liftF'
    --
    -- @
    -- 'retract' . 'liftF' = 'id'
    -- @
    #if __GLASGOW_HASKELL__ < 710
    retract :: (Functor f, Monad f) => F f a -> f a
    #else
    retract :: Monad f => F f a -> f a
    #endif
    retract :: F f a -> f a
    retract m :: F f a
    m = F f a -> (a -> f a) -> (f (f a) -> f a) -> f a
    forall (f :: * -> *) a.
    Functor f =>
    F f a -> forall r. (a -> r) -> (f r -> r) -> r
    runF F f a
    m a -> f a
    forall (m :: * -> *) a. Monad m => a -> m a
    return f (f a) -> f a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join
    {-# INLINE retract #-}

    -- | Tear down a free monad transformer using iteration over a transformer.
    retractT :: (MonadTrans t, Monad (t m), Monad m) => FT (t m) m a -> t m a
    retractT :: FT (t m) m a -> t m a
    retractT (FT m :: forall r.
    (a -> m r) -> (forall x. (x -> m r) -> t m x -> m r) -> m r
    m) = t m (t m a) -> t m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (t m (t m a) -> t m a)
    -> (m (t m a) -> t m (t m a)) -> m (t m a) -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (t m a) -> t m (t m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (t m a) -> t m a) -> m (t m a) -> t m a
    forall a b. (a -> b) -> a -> b
    $ (a -> m (t m a))
    -> (forall x. (x -> m (t m a)) -> t m x -> m (t m a)) -> m (t m a)
    forall r.
    (a -> m r) -> (forall x. (x -> m r) -> t m x -> m r) -> m r
    m (t m a -> m (t m a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (t m a -> m (t m a)) -> (a -> t m a) -> a -> m (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> t m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return) (\xg :: x -> m (t m a)
    xg xf :: t m x
    xf -> t m a -> m (t m a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (t m a -> m (t m a)) -> t m a -> m (t m a)
    forall a b. (a -> b) -> a -> b
    $ t m x
    xf t m x -> (x -> t m a) -> t m a
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= t m (t m a) -> t m a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (t m (t m a) -> t m a) -> (x -> t m (t m a)) -> x -> t m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (t m a) -> t m (t m a)
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m (t m a) -> t m (t m a)) -> (x -> m (t m a)) -> x -> t m (t m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . x -> m (t m a)
    xg)

    -- | Tear down an 'F' 'Monad' using iteration.
    iter :: Functor f => (f a -> a) -> F f a -> a
    iter :: (f a -> a) -> F f a -> a
    iter phi :: f a -> a
    phi = Identity a -> a
    forall a. Identity a -> a
    runIdentity (Identity a -> a) -> (F f a -> Identity a) -> F f a -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (f (Identity a) -> Identity a) -> F f a -> Identity a
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, Monad m) =>
    (f (m a) -> m a) -> FT f m a -> m a
    iterT (a -> Identity a
    forall a. a -> Identity a
    Identity (a -> Identity a)
    -> (f (Identity a) -> a) -> f (Identity a) -> Identity a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . f a -> a
    phi (f a -> a) -> (f (Identity a) -> f a) -> f (Identity a) -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Identity a -> a) -> f (Identity a) -> f a
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Identity a -> a
    forall a. Identity a -> a
    runIdentity)
    {-# INLINE iter #-}

    -- | Like 'iter' for monadic values.
    iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> F f a -> m a
    iterM :: (f (m a) -> m a) -> F f a -> m a
    iterM phi :: f (m a) -> m a
    phi = (f (m a) -> m a) -> FT f m a -> m a
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, Monad m) =>
    (f (m a) -> m a) -> FT f m a -> m a
    iterT f (m a) -> m a
    phi (FT f m a -> m a) -> (F f a -> FT f m a) -> F f a -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (forall a. Identity a -> m a) -> F f a -> FT f m a
    forall (m :: * -> *) (n :: * -> *) (f :: * -> *) b.
    (Monad m, Monad n) =>
    (forall a. m a -> n a) -> FT f m b -> FT f n b
    hoistFT (a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (a -> m a) -> (Identity a -> a) -> Identity a -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Identity a -> a
    forall a. Identity a -> a
    runIdentity)

    -- | Convert to another free monad representation.
    fromF :: (Functor f, MonadFree f m) => F f a -> m a
    fromF :: F f a -> m a
    fromF m :: F f a
    m = F f a -> (a -> m a) -> (f (m a) -> m a) -> m a
    forall (f :: * -> *) a.
    Functor f =>
    F f a -> forall r. (a -> r) -> (f r -> r) -> r
    runF F f a
    m a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return f (m a) -> m a
    forall (f :: * -> *) (m :: * -> *) a.
    MonadFree f m =>
    f (m a) -> m a
    wrap
    {-# INLINE fromF #-}

    -- | Generate a Church-encoded free monad from a 'Free' monad.
    toF :: Free f a -> F f a
    toF :: Free f a -> F f a
    toF = Free f a -> F f a
    forall (m :: * -> *) (f :: * -> *) a.
    Monad m =>
    FreeT f m a -> FT f m a
    toFT
    {-# INLINE toF #-}

    -- | Improve the asymptotic performance of code that builds a free monad with only binds and returns by using 'F' behind the scenes.
    --
    -- This is based on the \"Free Monads for Less\" series of articles by Edward Kmett:
    --
    -- <http://comonad.com/reader/2011/free-monads-for-less/>
    -- <http://comonad.com/reader/2011/free-monads-for-less-2/>
    --
    -- and \"Asymptotic Improvement of Computations over Free Monads\" by Janis Voightländer:
    --
    -- <http://www.iai.uni-bonn.de/~jv/mpc08.pdf>
    improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
    improve :: (forall (m :: * -> *). MonadFree f m => m a) -> Free f a
    improve m :: forall (m :: * -> *). MonadFree f m => m a
    m = F f a -> Free f a
    forall (f :: * -> *) (m :: * -> *) a.
    (Functor f, MonadFree f m) =>
    F f a -> m a
    fromF F f a
    forall (m :: * -> *). MonadFree f m => m a
    m
    {-# INLINE improve #-}

    -- | Improve the asymptotic performance of code that builds a free monad transformer
    -- with only binds and returns by using 'FT' behind the scenes.
    --
    -- Similar to 'improve'.
    improveT :: (Functor f, Monad m) => (forall t. MonadFree f (t m) => t m a) -> FreeT f m a
    improveT :: (forall (t :: (* -> *) -> * -> *). MonadFree f (t m) => t m a)
    -> FreeT f m a
    improveT m :: forall (t :: (* -> *) -> * -> *). MonadFree f (t m) => t m a
    m = FT f m a -> FreeT f m a
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, Functor f) =>
    FT f m a -> FreeT f m a
    fromFT FT f m a
    forall (t :: (* -> *) -> * -> *). MonadFree f (t m) => t m a
    m
    {-# INLINE improveT #-}