{-# LANGUAGE Safe #-}

-- | Definitions and instances that use direct recursion, which (because of
--   laziness) can lead to non-termination.
module Yaya.Unsafe.Fold
  ( anaM,
    corecursivePrism,
    ganaM,
    ghylo,
    ghyloM,
    hylo,
    hyloM,
    stream',
    streamAna,
    streamGApo,
    unsafeAna,
    unsafeCata,
  )
where

import "base" Control.Applicative (Applicative (pure))
import "base" Control.Category (Category ((.)))
import "base" Control.Monad (Monad, (<=<))
import "base" Data.Function (flip, ($))
import "base" Data.Functor (Functor (fmap))
import "base" Data.Functor.Compose (Compose (Compose, getCompose))
import "base" Data.Traversable (Traversable (sequenceA))
import "comonad" Control.Comonad (Comonad (extract))
import "lens" Control.Lens (Prism', matching, prism, review)
import "yaya" Yaya.Fold
  ( Algebra,
    AlgebraM,
    Coalgebra,
    CoalgebraM,
    CoalgebraPrism,
    Corecursive (ana),
    DistributiveLaw,
    GAlgebra,
    GAlgebraM,
    GCoalgebra,
    GCoalgebraM,
    Projectable (project),
    Recursive (cata),
    Steppable (embed),
    lowerAlgebra,
    lowerAlgebraM,
    lowerCoalgebra,
    lowerCoalgebraM,
  )
import "yaya" Yaya.Pattern (Maybe, Pair, maybe, uncurry)

-- | Instances leak transitively, so while "Yaya.Unsafe.Fold.Instances" exists,
--   it should only be used when it is unavoidable. If you are explicitly
--   folding a structure unsafely, use this function instead of importing that
--   module.
unsafeAna :: (Steppable (->) t f, Functor f) => Coalgebra (->) f a -> a -> t
unsafeAna :: forall t (f :: * -> *) a.
(Steppable (->) t f, Functor f) =>
Coalgebra (->) f a -> a -> t
unsafeAna = Algebra (->) f t -> Coalgebra (->) f a -> a -> t
forall (f :: * -> *) b a.
Functor f =>
Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo Algebra (->) f t
forall {k} (c :: k -> k -> *) (t :: k) (f :: k -> k).
Steppable c t f =>
Algebra c f t
embed

-- | Instances leak transitively, so while "Yaya.Unsafe.Fold.Instances" exists,
--   it should only be used when it is unavoidable. If you are explicitly
--   unfolding a structure unsafely, use this function instead of importing that
--   module.
--
--   Should one prefer `unsafeAna` or `unsafeCata` in cases where both are
--   applicable?
-- - one may provide weaker constraints than the other in certain cases (e.g.,
--   on its own, `unsafeCata` only requires `Projectable` on the source, but
--  `unsafeAna` requires `Steppable` on the target. Depending on what other
--   constraints already exist on the function, either one may ultimately be
--   less constrained.
-- - they may fail differently: `unsafeCata` (folding a potentially-infinite
--   structure) is likely to result in non-termination, whereas `unsafeAna`
--   (building a potentially-infinite structure strictly) is likely to use up
--   the memory or overflow the stack.
unsafeCata :: (Projectable (->) t f, Functor f) => Algebra (->) f a -> t -> a
unsafeCata :: forall t (f :: * -> *) a.
(Projectable (->) t f, Functor f) =>
Algebra (->) f a -> t -> a
unsafeCata = (Algebra (->) f a -> Coalgebra (->) f t -> t -> a)
-> Coalgebra (->) f t -> Algebra (->) f a -> t -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Algebra (->) f a -> Coalgebra (->) f t -> t -> a
forall (f :: * -> *) b a.
Functor f =>
Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo Coalgebra (->) f t
forall {k} {k1} (c :: k -> k1 -> *) (t :: k) (f :: k -> k1).
Projectable c t f =>
Coalgebra c f t
project

-- | This can’t be implemented in a total fashion. There is a /similar/ approach
--   that can be total – with @ψ :: `CoalgebraM` (->) m f a@, @`ana` (`Compose`
--  . ψ)@ results in something like @`Nu` (`Compose` m f)@ which is akin to an
--   effectful stream.
anaM ::
  (Monad m, Steppable (->) t f, Traversable f) =>
  CoalgebraM (->) m f a ->
  a ->
  m t
anaM :: forall (m :: * -> *) t (f :: * -> *) a.
(Monad m, Steppable (->) t f, Traversable f) =>
CoalgebraM (->) m f a -> a -> m t
anaM = AlgebraM (->) m f t -> CoalgebraM (->) m f a -> a -> m t
forall (m :: * -> *) (f :: * -> *) b a.
(Monad m, Traversable f) =>
AlgebraM (->) m f b -> CoalgebraM (->) m f a -> a -> m b
hyloM (t -> m t
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (t -> m t) -> (f t -> t) -> AlgebraM (->) m f t
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. f t -> t
forall {k} (c :: k -> k -> *) (t :: k) (f :: k -> k).
Steppable c t f =>
Algebra c f t
embed)

ganaM ::
  (Monad m, Monad n, Traversable n, Steppable (->) t f, Traversable f) =>
  DistributiveLaw (->) n f ->
  GCoalgebraM (->) m n f a ->
  a ->
  m t
ganaM :: forall (m :: * -> *) (n :: * -> *) t (f :: * -> *) a.
(Monad m, Monad n, Traversable n, Steppable (->) t f,
 Traversable f) =>
DistributiveLaw (->) n f -> GCoalgebraM (->) m n f a -> a -> m t
ganaM DistributiveLaw (->) n f
k GCoalgebraM (->) m n f a
ψ = CoalgebraM (->) m f (n a) -> n a -> m t
forall (m :: * -> *) t (f :: * -> *) a.
(Monad m, Steppable (->) t f, Traversable f) =>
CoalgebraM (->) m f a -> a -> m t
anaM (DistributiveLaw (->) n f
-> GCoalgebraM (->) m n f a -> CoalgebraM (->) m f (n a)
forall (m :: * -> *) (f :: * -> *) (n :: * -> *) a.
(Applicative m, Traversable f, Monad n, Traversable n) =>
DistributiveLaw (->) n f
-> GCoalgebraM (->) m n f a -> CoalgebraM (->) m f (n a)
lowerCoalgebraM n (f a) -> f (n a)
DistributiveLaw (->) n f
k GCoalgebraM (->) m n f a
ψ) (n a -> m t) -> (a -> n a) -> a -> m t
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> n a
forall a. a -> n a
forall (f :: * -> *) a. Applicative f => a -> f a
pure

-- | Fusion of an 'ana' and a 'cata'.
hylo :: (Functor f) => Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo :: forall (f :: * -> *) b a.
Functor f =>
Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo Algebra (->) f b
φ Coalgebra (->) f a
ψ = a -> b
go
  where
    go :: a -> b
go = Algebra (->) f b
φ Algebra (->) f b -> (a -> f b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a -> b) -> f a -> f b
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
go (f a -> f b) -> Coalgebra (->) f a -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Coalgebra (->) f a
ψ

ghylo ::
  (Comonad w, Monad m, Functor f) =>
  DistributiveLaw (->) f w ->
  DistributiveLaw (->) m f ->
  GAlgebra (->) w f b ->
  GCoalgebra (->) m f a ->
  a ->
  b
ghylo :: forall (w :: * -> *) (m :: * -> *) (f :: * -> *) b a.
(Comonad w, Monad m, Functor f) =>
DistributiveLaw (->) f w
-> DistributiveLaw (->) m f
-> GAlgebra (->) w f b
-> GCoalgebra (->) m f a
-> a
-> b
ghylo DistributiveLaw (->) f w
w DistributiveLaw (->) m f
m GAlgebra (->) w f b
φ GCoalgebra (->) m f a
ψ =
  w b -> b
forall a. w a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract (w b -> b) -> (a -> w b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Algebra (->) f (w b) -> Coalgebra (->) f (m a) -> m a -> w b
forall (f :: * -> *) b a.
Functor f =>
Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo (DistributiveLaw (->) f w
-> GAlgebra (->) w f b -> Algebra (->) f (w b)
forall (f :: * -> *) (w :: * -> *) a.
(Functor f, Comonad w) =>
DistributiveLaw (->) f w
-> GAlgebra (->) w f a -> Algebra (->) f (w a)
lowerAlgebra f (w a) -> w (f a)
DistributiveLaw (->) f w
w GAlgebra (->) w f b
φ) (DistributiveLaw (->) m f
-> GCoalgebra (->) m f a -> Coalgebra (->) f (m a)
forall (f :: * -> *) (m :: * -> *) a.
(Functor f, Monad m) =>
DistributiveLaw (->) m f
-> GCoalgebra (->) m f a -> Coalgebra (->) f (m a)
lowerCoalgebra m (f a) -> f (m a)
DistributiveLaw (->) m f
m GCoalgebra (->) m f a
ψ) (m a -> w b) -> (a -> m a) -> a -> w b
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> m a
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure

hyloM ::
  (Monad m, Traversable f) =>
  AlgebraM (->) m f b ->
  CoalgebraM (->) m f a ->
  a ->
  m b
hyloM :: forall (m :: * -> *) (f :: * -> *) b a.
(Monad m, Traversable f) =>
AlgebraM (->) m f b -> CoalgebraM (->) m f a -> a -> m b
hyloM AlgebraM (->) m f b
φ CoalgebraM (->) m f a
ψ = Algebra (->) (Compose m f) (m b)
-> Coalgebra (->) (Compose m f) a -> a -> m b
forall (f :: * -> *) b a.
Functor f =>
Algebra (->) f b -> Coalgebra (->) f a -> a -> b
hylo (AlgebraM (->) m f b
φ AlgebraM (->) m f b
-> (Compose m f (m b) -> m (f b))
-> Algebra (->) (Compose m f) (m b)
forall (m :: * -> *) b c a.
Monad m =>
(b -> m c) -> (a -> m b) -> a -> m c
<=< f (m b) -> m (f b)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a. Applicative f => f (f a) -> f (f a)
sequenceA (f (m b) -> m (f b))
-> (Compose m f (m b) -> m (f (m b)))
-> Compose m f (m b)
-> m (f b)
forall (m :: * -> *) b c a.
Monad m =>
(b -> m c) -> (a -> m b) -> a -> m c
<=< Compose m f (m b) -> m (f (m b))
forall {k1} {k2} (f :: k1 -> *) (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose) (m (f a) -> Compose m f a
forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (m (f a) -> Compose m f a)
-> CoalgebraM (->) m f a -> Coalgebra (->) (Compose m f) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CoalgebraM (->) m f a
ψ)

ghyloM ::
  (Comonad w, Traversable w, Monad m, Traversable f, Monad n, Traversable n) =>
  DistributiveLaw (->) f w ->
  DistributiveLaw (->) n f ->
  GAlgebraM (->) m w f b ->
  GCoalgebraM (->) m n f a ->
  a ->
  m b
ghyloM :: forall (w :: * -> *) (m :: * -> *) (f :: * -> *) (n :: * -> *) b a.
(Comonad w, Traversable w, Monad m, Traversable f, Monad n,
 Traversable n) =>
DistributiveLaw (->) f w
-> DistributiveLaw (->) n f
-> GAlgebraM (->) m w f b
-> GCoalgebraM (->) m n f a
-> a
-> m b
ghyloM DistributiveLaw (->) f w
w DistributiveLaw (->) n f
n GAlgebraM (->) m w f b
φ GCoalgebraM (->) m n f a
ψ =
  (w b -> b) -> m (w b) -> m b
forall a b. (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap w b -> b
forall a. w a -> a
forall (w :: * -> *) a. Comonad w => w a -> a
extract (m (w b) -> m b) -> (a -> m (w b)) -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. AlgebraM (->) m f (w b)
-> CoalgebraM (->) m f (n a) -> n a -> m (w b)
forall (m :: * -> *) (f :: * -> *) b a.
(Monad m, Traversable f) =>
AlgebraM (->) m f b -> CoalgebraM (->) m f a -> a -> m b
hyloM (DistributiveLaw (->) f w
-> GAlgebraM (->) m w f b -> AlgebraM (->) m f (w b)
forall (m :: * -> *) (f :: * -> *) (w :: * -> *) a.
(Applicative m, Traversable f, Comonad w, Traversable w) =>
DistributiveLaw (->) f w
-> GAlgebraM (->) m w f a -> AlgebraM (->) m f (w a)
lowerAlgebraM f (w a) -> w (f a)
DistributiveLaw (->) f w
w GAlgebraM (->) m w f b
φ) (DistributiveLaw (->) n f
-> GCoalgebraM (->) m n f a -> CoalgebraM (->) m f (n a)
forall (m :: * -> *) (f :: * -> *) (n :: * -> *) a.
(Applicative m, Traversable f, Monad n, Traversable n) =>
DistributiveLaw (->) n f
-> GCoalgebraM (->) m n f a -> CoalgebraM (->) m f (n a)
lowerCoalgebraM n (f a) -> f (n a)
DistributiveLaw (->) n f
n GCoalgebraM (->) m n f a
ψ) (n a -> m (w b)) -> (a -> n a) -> a -> m (w b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> n a
forall a. a -> n a
forall (f :: * -> *) a. Applicative f => a -> f a
pure

-- | This is the core operation for all metamorphisms. It generally shouldn’t be
--   used directly, but is exposed in case you come up with a novel accumulation
--   function to use.
--
--   Metamorphisms are conceptually a fold followed by an unfold (effectively
--   the reverse of a hylomorphism). Many are equivalent to @`ana` ψ `.` `cata`
--   φ@, but some can be processed incrementally, forming a family of
--   “[streaming
--   metamorphisms](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/metamorphisms-scp.pdf)”,
--   which are the ones captured here.
--
--  __FIXME__: What happens when this is given a branching structure? Where does
--             that cause a problem?
--
--  __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b
--          for some commentary and explanation.
stream' ::
  ( Projectable (->) input inputf,
    Steppable (->) output outputf,
    Functor outputf
  ) =>
  -- | Lazily processes the state into additional output elements. This should
  --   return `Nothing` when the state doesn’t allow any more output to be
  --   generated, causing control to be transferred back to the accumulator
  --   algebra.
  --
  -- > state -> Maybe (outputf state)
  CoalgebraM (->) Maybe outputf state ->
  -- | The general state accumulation function, this is specialized in the other
  --   @stream*@ functions. Given a state and a continuation function, converts
  --   the entire input to output.
  --
  --  __TODO__: Consider whether it’d be useful/possible to use
  --
  --          > forall x. state -> ((state -> state) -> x -> output) -> inputf x -> output
  --
  --            to prevent the function from consuming more than one element of
  --            the input per call.
  (state -> ((state -> state) -> input -> output) -> inputf input -> output) ->
  -- | The initial state.
  state ->
  -- | The `Recursive` (well, `Projectable`) input.
  input ->
  -- | The `Corecursive` (well, `Steppable`) output.
  output
stream' :: forall input (inputf :: * -> *) output (outputf :: * -> *) state.
(Projectable (->) input inputf, Steppable (->) output outputf,
 Functor outputf) =>
CoalgebraM (->) Maybe outputf state
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
stream' CoalgebraM (->) Maybe outputf state
process state
-> ((state -> state) -> input -> output) -> inputf input -> output
accum = state -> input -> output
go
  where
    go :: state -> input -> output
go state
state input
input =
      output
-> (outputf state -> output) -> Maybe (outputf state) -> output
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
        (state
-> ((state -> state) -> input -> output) -> inputf input -> output
accum state
state (state -> input -> output
go (state -> input -> output)
-> ((state -> state) -> state)
-> (state -> state)
-> input
-> output
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ((state -> state) -> state -> state
forall a b. (a -> b) -> a -> b
$ state
state)) (Coalgebra (->) inputf input
forall {k} {k1} (c :: k -> k1 -> *) (t :: k) (f :: k -> k1).
Projectable c t f =>
Coalgebra c f t
project input
input))
        (Algebra (->) outputf output
forall {k} (c :: k -> k -> *) (t :: k) (f :: k -> k).
Steppable c t f =>
Algebra c f t
embed Algebra (->) outputf output
-> (outputf state -> outputf output) -> outputf state -> output
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (state -> output) -> outputf state -> outputf output
forall a b. (a -> b) -> outputf a -> outputf b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (state -> input -> output
`go` input
input))
        (Maybe (outputf state) -> output)
-> Maybe (outputf state) -> output
forall a b. (a -> b) -> a -> b
$ CoalgebraM (->) Maybe outputf state
process state
state

-- | Gibbons’ metamorphism. It lazily folds a (necessarily infinite) value,
--   incrementally re-expanding that value into some new representation. See
--  `stream'` for more on metamorphisms.
--
--  __FIXME__: What happens when this is given a finite structure?
--
--   The “Ana” in the name parallels the naming of `streamGApo`, where this form
--   lacks the helper algebra, in the same way that `ana` lacks the helper
--   algebra that `Yaya.Zoo.gapo` has.
streamAna ::
  ( Projectable (->) input inputf,
    Steppable (->) output outputf,
    Functor outputf
  ) =>
  -- | Lazily processes the state into additional output elements. This should
  --   return `Nothing` when the state doesn’t allow any more output to be
  --   generated, causing control to be transferred back to the accumulator
  --   algebra.
  --
  -- > state -> Maybe (outputf state)
  CoalgebraM (->) Maybe outputf state ->
  -- | Accumulates more elements from the input into the state. It returns a
  --   function to modify the previous state as well as the remaining input.
  --   This passes control back to the processing coalgebra after each call,
  --   allowing as much output to be generated from as little input as possible.
  --
  -- > inputf input -> (state -> state, input)
  AlgebraM (->) (Pair (state -> state)) inputf input ->
  -- | The initial state.
  state ->
  -- | The `Recursive` (well, `Projectable`) input.
  input ->
  -- | The `Corecursive` (well, `Steppable`) output.
  output
streamAna :: forall input (inputf :: * -> *) output (outputf :: * -> *) state.
(Projectable (->) input inputf, Steppable (->) output outputf,
 Functor outputf) =>
CoalgebraM (->) Maybe outputf state
-> AlgebraM (->) (Pair (state -> state)) inputf input
-> state
-> input
-> output
streamAna CoalgebraM (->) Maybe outputf state
process AlgebraM (->) (Pair (state -> state)) inputf input
accum = CoalgebraM (->) Maybe outputf state
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
forall input (inputf :: * -> *) output (outputf :: * -> *) state.
(Projectable (->) input inputf, Steppable (->) output outputf,
 Functor outputf) =>
CoalgebraM (->) Maybe outputf state
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
stream' CoalgebraM (->) Maybe outputf state
process ((state
  -> ((state -> state) -> input -> output) -> inputf input -> output)
 -> state -> input -> output)
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
forall a b. (a -> b) -> a -> b
$ \state
_state (state -> state) -> input -> output
cont -> ((state -> state) -> input -> output)
-> Pair (state -> state) input -> output
forall a b c. (a -> b -> c) -> Pair a b -> c
uncurry (state -> state) -> input -> output
cont (Pair (state -> state) input -> output)
-> AlgebraM (->) (Pair (state -> state)) inputf input
-> inputf input
-> output
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. AlgebraM (->) (Pair (state -> state)) inputf input
accum

-- | Another form of Gibbons’ metamorphism. This one can be applied to non-
--   infinite inputs and takes an additional “flushing” coalgebra to be applied
--   after all the input has been consumed. See `stream'` for more on
--  metamorphisms.
--
--   The “GApo” in the name comes from the parallel with `Yaya.Zoo.gapo`, where
--   a “helper” `Coalgebra` (the “flusher” in this case) can be applied when the
--   primary algebra “fails”. This is also why the arguments are re-ordered
--   relative to Gibbons’ `Yaya.Unsafe.Zoo.fstream` – to make the parallel with
--   @gapo@ more obvious.
streamGApo ::
  ( Projectable (->) input inputf,
    Steppable (->) output outputf,
    Corecursive (->) output outputf,
    Functor outputf
  ) =>
  -- | The flushing coalgebra that consumes the remaining state after the input
  --   has been fully consumed.
  Coalgebra (->) outputf state ->
  -- | Lazily processes the state into additional output elements. This should
  --   return `Nothing` when the state doesn’t allow any more output to be
  --   generated, causing control to be transferred back to the accumulator
  --   algebra.
  --
  -- > state -> Maybe (outputf state)
  CoalgebraM (->) Maybe outputf state ->
  -- | Accumulates more elements from the input into the state. It returns a
  --   function to modify the previous state as well as the remaining input.
  --   This passes control back to the processing coalgebra after each call,
  --   allowing as much output to be generated from as little input as possible.
  --   This should return `Nothing` when the input is consumed, causing control
  --   to be transferred to the flushing coalgebra instead of the processing
  --   coalgebra.
  (inputf input -> Maybe (Pair (state -> state) input)) ->
  -- | The initial state.
  state ->
  -- | The `Recursive` (well, `Projectable`) input.
  input ->
  -- | The `Corecursive` output.
  output
streamGApo :: forall input (inputf :: * -> *) output (outputf :: * -> *) state.
(Projectable (->) input inputf, Steppable (->) output outputf,
 Corecursive (->) output outputf, Functor outputf) =>
Coalgebra (->) outputf state
-> CoalgebraM (->) Maybe outputf state
-> (inputf input -> Maybe (Pair (state -> state) input))
-> state
-> input
-> output
streamGApo Coalgebra (->) outputf state
flush CoalgebraM (->) Maybe outputf state
process inputf input -> Maybe (Pair (state -> state) input)
accum =
  CoalgebraM (->) Maybe outputf state
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
forall input (inputf :: * -> *) output (outputf :: * -> *) state.
(Projectable (->) input inputf, Steppable (->) output outputf,
 Functor outputf) =>
CoalgebraM (->) Maybe outputf state
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
stream' CoalgebraM (->) Maybe outputf state
process ((state
  -> ((state -> state) -> input -> output) -> inputf input -> output)
 -> state -> input -> output)
-> (state
    -> ((state -> state) -> input -> output) -> inputf input -> output)
-> state
-> input
-> output
forall a b. (a -> b) -> a -> b
$
    \state
state (state -> state) -> input -> output
cont -> output
-> (Pair (state -> state) input -> output)
-> Maybe (Pair (state -> state) input)
-> output
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Coalgebra (->) outputf state -> state -> output
forall a. Coalgebra (->) outputf a -> a -> output
forall {k} {k1} (c :: k -> k1 -> *) (t :: k1) (f :: k -> k1)
       (a :: k).
Corecursive c t f =>
Coalgebra c f a -> c a t
ana Coalgebra (->) outputf state
flush state
state) (((state -> state) -> input -> output)
-> Pair (state -> state) input -> output
forall a b c. (a -> b -> c) -> Pair a b -> c
uncurry (state -> state) -> input -> output
cont) (Maybe (Pair (state -> state) input) -> output)
-> (inputf input -> Maybe (Pair (state -> state) input))
-> inputf input
-> output
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. inputf input -> Maybe (Pair (state -> state) input)
accum

corecursivePrism ::
  (Steppable (->) t f, Recursive (->) t f, Traversable f) =>
  CoalgebraPrism f a ->
  Prism' a t
corecursivePrism :: forall t (f :: * -> *) a.
(Steppable (->) t f, Recursive (->) t f, Traversable f) =>
CoalgebraPrism f a -> Prism' a t
corecursivePrism CoalgebraPrism f a
alg = (t -> a) -> (a -> Either a t) -> Prism a a t t
forall b t s a. (b -> t) -> (s -> Either t a) -> Prism s t a b
prism (Algebra (->) f a -> t -> a
forall a. Algebra (->) f a -> t -> a
forall {k} {k1} (c :: k -> k1 -> *) (t :: k) (f :: k1 -> k)
       (a :: k1).
Recursive c t f =>
Algebra c f a -> c t a
cata (Algebra (->) f a -> t -> a) -> Algebra (->) f a -> t -> a
forall a b. (a -> b) -> a -> b
$ AReview a (f a) -> Algebra (->) f a
forall b (m :: * -> *) t. MonadReader b m => AReview t b -> m t
review AReview a (f a)
CoalgebraPrism f a
alg) (CoalgebraM (->) (Either a) f a -> a -> Either a t
forall (m :: * -> *) t (f :: * -> *) a.
(Monad m, Steppable (->) t f, Traversable f) =>
CoalgebraM (->) m f a -> a -> m t
anaM (CoalgebraM (->) (Either a) f a -> a -> Either a t)
-> CoalgebraM (->) (Either a) f a -> a -> Either a t
forall a b. (a -> b) -> a -> b
$ APrism a a (f a) (f a) -> CoalgebraM (->) (Either a) f a
forall s t a b. APrism s t a b -> s -> Either t a
matching APrism a a (f a) (f a)
CoalgebraPrism f a
alg)