```\begin{comment}
\begin{code}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RecordWildCards #-}

module LiveCoding.Coalgebra where

-- base
import Control.Arrow (second)
import Data.Data

-- essence-of-live-coding
import LiveCoding.Cell

\end{code}
\end{comment}

\section{Monadic stream functions and final coalgebras}

\label{sec:msfs and final coalgebras}

But can they fill their footsteps completely in terms of expressiveness?
If not, which programs exactly can be represented as \mintinline{haskell}{MSF}s and which can't?
To find the answer to these questions,
let us reexamine both types.

With the help of a simple type synonym,
the \mintinline{haskell}{MSF} definition can be recast in explicit fixpoint form:

\begin{code}
type StateTransition m a b s = a -> m (b, s)

data MSF m a b = MSF
{ unMSF :: StateTransition m a b (MSF m a b)
}
\end{code}
This definition tells us that monadic stream functions are so-called \emph{final coalgebras} of the \mintinline{haskell}{StateTransition} functor
An ordinary coalgebra for this functor is given by some type \mintinline{haskell}{s} and a coalgebra structure map:
\begin{code}
data Coalg m a b where
Coalg
:: s
-> (s -> StateTransition m a b s)
-> Coalg m a b
\end{code}
But hold on, the astute reader will intercept,
is this not simply the definition of \mintinline{haskell}{Cell}?
Alas, it is not, for it lacks the type class restriction \mintinline{haskell}{Data s},
which we need so dearly for the type migration.
Any cell is a coalgebra,
but only those coalgebras that satisfy this type class are a cell.

Oh, if only there were no such distinction.
By the very property of the final coalgebra,
we can embed every coalgebra therein:
\begin{code}
finality :: Monad m => Coalg m a b -> MSF m a b
finality (Coalg state step) = MSF \$ \a -> do
(b, state') <- step state a
return (b, finality \$ Coalg state' step)
\end{code}
And analogously, every cell can be easily made into an \mintinline{haskell}{MSF} without loss of information:
\begin{code}
finalityC :: Monad m => Cell m a b -> MSF m a b
finalityC Cell { .. } = MSF \$ \a -> do
(b, cellState') <- cellStep cellState a
return (b, finalityC \$ Cell cellState' cellStep)
\end{code}
And the final coalgebra is of course a mere coalgebra itself:
\begin{code}
coalgebra :: MSF m a b -> Coalg m a b
coalgebra msf = Coalg msf unMSF
\end{code}
\begin{code}
coalgebraC
:: Data (MSF m a b)
=> MSF m a b
-> Cell m a b
coalgebraC msf = Cell msf unMSF
\end{code}
We are out of luck if we would want to derive an instance of \mintinline{haskell}{Data (MSF m a b)}.
Monadic stream functions are, well, functions,
and therefore have no \mintinline{haskell}{Data} instance.
The price of \mintinline{haskell}{Data} is loss of higher-order state.
Just how big this loss is will be demonstrated in the following section.

\begin{comment}
\subsection{Initial algebras}

\begin{code}
type AlgStructure m a b s = StateTransition m a b s -> s
data Alg m a b where
Alg
:: s
-> AlgStructure m a b s
-> Alg m a b

algMSF :: MSF m a b -> Alg m a b
algMSF msf = Alg msf MSF

-- TODO Could explain better why this is simpler in the coalgebra case
initiality
:: Functor m
=> AlgStructure m a b s
-> MSF m a b
-> s
initiality algStructure = go
where
go msf = algStructure \$ \a -> second go <\$> unMSF msf a

\end{code}
\end{comment}
```