### New code
The trick is to take a regular functor `f` and create a new functor whose `fmap` is lazily evaluated.
Here's the usual `Fix`
```scala=
case class Fix[F[_]](inner: F[Fix[F]])
object Fix {
def in[F[_]](lff: F[Fix[F]]): Fix[F] = new Fix[F](lff)
def out[F[_]]: Fix[F] => F[Fix[F]] = f => f.inner
}
```
Lazify takes a functor `f` and produces a new functor `Lazify f`
```haskell
newtype Lazify f a = LZ (f (Lazy a))
-- LZ :: f (Lazy a) -> Lazify f a
unLazify :: Lazify f a -> f (Lazy a)
unLazify (LZ fla) = fla
```
```scala=
type Lazy[A] = () => A
def force[A](la: Lazy[A]) = la()
```
`Lazy` is actually a functor
```scala=
implicit def functorForLazy[A]: Functor[Lazy[*]] =
new Functor[Lazy[*]]
{
def map[A, C]
(la: Lazy[A])(f: A => C): Lazy[C]
= {
() => f(force(la))
}
}
```
```scala=
case class Lazify [F[_], A](sus: F[Lazy [A]])
def lazify[F[_], A]
(fla: F[Lazy[A]]): Lazify[F, A]
= new Lazify[F, A](fla)
def unLazify[F[_], A]:
Lazify[F, A] => F[Lazy[A]]
= la => la.sus
```
```haskell
instance Functor f => Functor (Lazify f) where
-- (a->b) -> Lazify f a -> Lazify f b
fmap g (LZ fla) = LZ (fmap (lazy . g . force) fla)
```
We use the `fmap` of the original functor `f`. To apply the function `g`, we have to first force the evaluation, then make the result lazy again.
This is the functor instance for a lazified functor:
```scala=
implicit def functorForLazify[F[_]: Functor, A]: Functor[Lazify[F, *]] =
new Functor[Lazify[F, *]]
{
def map[A, C]
(lfa: Lazify[F, A])(f: A => C): Lazify[F, C]
= {
val fa = lfa.sus // F[Lazy[A]] or F[()=>A]
// transform lazy values to lazy values using g
def trans[A, C]
(g: A=>C) (la: ()=>A): Lazy[C]
= {
() => (g (force (la)))
}
val y = fa.map(trans[A,C](f)) // F[Lazy[C]]
lazify(y)
}
}
```
Or, we can express it as functor composition:
```scala=
implicit def functorForLazify[F[_]: Functor, A]: Functor[Lazify[F, *]] =
new Functor[Lazify[F, *]]
{
def map[A, C]
(lfa: Lazify[F, A])(f: A => C): Lazify[F, C]
= {
val fa = lfa.sus // F[Lazy[A]] or F[()=>A]
val y = Functor[F].compose[Lazy].map(fa)(f)
lazify(y)
}
}
```
We use the usual definition of `Fix`, but we apply it to the lazified functor. This is the smart constructor
```haskell
fix :: Functor f => f (Fix (Lazify f)) -> Fix (Lazify f)
fix = Fix . LZ . fmap lazy
```
```scala=
def fix[F[_]: Functor](ff: F[Fix[F]]) : Fix[F] = Fix.in(ff)
```
This is just regular anamorphism, but we apply it to the lazified functor
```haskell
ana :: Functor f => Coalgebra f a -> a -> Fix (Lazify f)
ana coa = fix . fmap (ana coa) . coa
```
This doesn't work. There should be a way to pass an implicit functor instance to `map`. The functor in question is `F`
```scala=
def ana[F[_]: Functor, A](coalg: Coalgebra[F, A])(a: A) : Fix[Lazify[F, *]]
= {
coalg.andThen(_.map(ana(coalg))).andThen(fix(_))(a)
}
```
### Examples
Start with the functor
```haskell
data IStreamF a = IStreamF Int a
deriving Functor
```
```scala=
sealed trait PairWithInt[A]
case class MkPair[A](h: Int, t: A) extends PairWithInt[A]
implicit def functorForPair[A]: Functor[PairWithInt[*]] =
new Functor[PairWithInt[*]] {
def map[A, C](fa: PairWithInt[A])(f: A => C): PairWithInt[C] = fa match {
case MkPair(head, tail) => {
MkPair(head, f(tail))
}
}
}
```
Define `IntLst` as a fixed point of the lazified version of `IStremF`
```haskell
type IntLst = Fix (Lazify IStreamF)
```
These are the accessors
```haskell
frst :: IStreamF a -> Int
frst (IStreamF n _) = n
scnd :: IStreamF a -> a
scnd (IStreamF _ a) = a
```
```scala=
def frst[A](stm: PairWithInt[A]) = stm match {
case MkPair(h, _) => h
}
def scnd[A](stm: PairWithInt[A]) = stm match {
case MkPair(_, t) => t
}
```
We can use a regular coalgebra
```haskell
natsCoa :: Coalgebra IStreamF Int
natsCoa n = IStreamF n (n+1)
```
```scala=
def natsCoa: Coalgebra[PairWithInt, Int] = { n =>
MkPair(n, n + 1)
}
```
and apply it to the lazified `IntLst`
```haskell
natsN :: Int -> IntLst
natsN n = ana natsCoa n
```
**This doesn't work**
I don't know how to pass `functorForLazify` to `ana`
```scala=
def natsN(n: Int): Fix[Lazify[PairWithInt, *]] = {
ana(natsCoa)(functorForLazify[PairWithInt])(n)
}
```
Helper functions that return the head and the (infinite) tail of the stream
```haskell
hd :: Fix (Lazify IStreamF) -> Int
hd = frst . unLazify. unFix
tl :: IntLst -> IntLst
tl = force . scnd . unLazify . unFix
```
```scala=
def hd: Fix[Lazify[PairWithInt, *]] => Int
= stm => frst(unLazify(Fix.out(stm)))
def tl: Fix[Lazify[PairWithInt, *]] => Fix[Lazify[PairWithInt, *]] = stm => {
force(scnd(unLazify(Fix.out(stm))))
}
```
Testing
```haskell
x = hd (tl (tl (natsN 0))) -- returns 2
```
### Primes
Sieve of Erathostenes
```haskell
era :: Coalgebra IStreamF IntLst
era nl = IStreamF h (lfilter (notdiv h) t)
where h = hd nl
t = tl nl
notdiv p n = n `mod` p /= 0
lfilter :: (Int -> Bool) -> IntLst -> IntLst
lfilter pred nl =
if pred h
then fix $ IStreamF h (lfilter pred t)
else lfilter pred (tl nl)
where h = hd nl
t = tl nl
primes :: IntLst
primes = ana era (natsN 2)
(hd.tl.tl.tl.tl) primes -- returns 11
```
# Recursion Schemes Categorically
## 3. Coalgebras and Anamorphisms
### Recursive Data Structures
There are two kinds of data structures: fixed-size and recursive.
Fixed-size are constructed using products and sums, or pairs and eithers.
Recursive data structures are like:
List(a) = Nil + a $\times$ List(a)
Tree(a) = Leaf + a $\times$ Tree(a) $\times$ Tree(a)
Natural numbers are recursive
Nat = Zero + Succ(Nat)
Things to do with recursive data structures:
* map
* filter
* fold (catamorphism)
* unfold (anamorphism)
Unfold creates a recursive data structure from seed.
Just like a tree grows from a seed. Every branch starts from a bud. The bud has the genetic information about the rest of the tree plus some state (epigenetic)
This is how you unfold a tree:
* start with a seed
* use a functor to
* decide what to do next (sum type)
* create a container of new seeds (product type)
### Coalgebras
A node of a recursive data structure is a container of (possibly smaller) versions of it. A node can be described as a functor. Filling the node with seeds, for a given functor $F$ is a function
$a \to F(a)$
where $a$ is the type of seed.
A coalgebra is a pair $(a, a \to F(a))$
$a$ is called the *carrier type* and the function is called the *structure map*.
Example: functor $F(a) = 1 + 2 \times a$
Here $1$ has just one value (a singleton) and $2$ has two values, conveniently named `True` and `False`
```haskell
data ListF a = Nil | Cons Bool a
deriving Functor
```
This is the functor that generates a list of `Bool` when `a` is replaced by a list.
Its coalgebra could be, for instance:
```haskell
coa1 :: Int -> ListF Int
coa1 n = if n == 0
then Nil
else Cons (even n) (n - 1)
```
The type `a` is called the carrier of the coalgebra: here it's `Int`. The function is called the *structure map*. Here it's `coa1`. Note: the structure map is *not* a polymorphic function.
We'll see later that this coalgebra generates a list of length n alternating between `True` and `False`
In general:
```scala=
type Coalgebra[F[_], A] = A => F[A]
```
```haskell
type Coalgebra f a = a -> f a
```
### Coalgebra Morphisms
We can define mappings of coalgebras. These are functions between carriers that preserve the structure of coalgebras. Consider two coalgebras $(a, \alpha \colon a \to F(a))$ and $(b, \beta \colon b \to F(b))$. The function $g \colon a \to b$ is an algebra morphism if $F(g) \circ \alpha = \beta \circ g$
Here, $F g$ is the lifting of $g$. In programming we call it `fmap g`.
For instance, let's take two coalgebras, one with the `Int` carrier
```haskell
coa1 :: Coalgebra ListF Int
coa1 n = if n == 0
then Nil
else Cons (even n) (n - 1)
```
and another with the `(Int, Bool)` carrier
```haskell
coa2 :: Coalgebra ListF (Int, Bool)
coa2 (n, b) = if n == 0
then Nil
else Cons (not b) (n - 1, not b)
```
The following function is an algebra morphism
```haskell
g :: Int -> (Int, Bool)
g n = (n, odd n)
```
You can check that, for instance,
```haskell
x1 = (fmap g . coa1) 4
x2 = (coa2 . g) 4
```
produce the same value `(True, (3, True))`
### Category of Coalgebras
Objects are coalgebras, arrows are coalgebra morphisms.
Coalgebra morphisms are composable (they are just functions, and commuting squares compose). Composition is associative. Identity function is a coalgebra morphism. $F(id) \circ \alpha = \alpha \circ id$
A terminal object in a category is defined as an object that has a unique incoming arrow from any object (including itself)
A terminal coalgebra $(t, j)$ has a unique coalgebra morphism from any coalgebra.
This unique morphism is called an *anamorphism*.
It's easy to prove that terminal coalgebra has the property of being invertible. (This result is called the Lambek's lemma.) The inverse function has the following signature
$j^{-1} \colon F t \to t$
An invertible function establishes the isomorphism between data types
$t \cong F t$
This equation tells us that $t$ is a *fixed point* of the functor $F$.
If we call $t$ `Fix[F]`, the fixed point of the functor `F`, we get the equation
```scala=
Fix[F] = F[Fix[F]])
```
```haskell
Fix f = f (Fix f)
```
We can use it to define `Fix f`
```haskell
newtype Fix f = Fix { unFix :: f (Fix f) }
```
`Fix f` is the carrier of a coalgebra with the structure map
```haskell
unFix :: Coalgebra f (Fix f)
unFix :: Fix f -> f (Fix f)
```
It's the inverse of the type constructor `Fix`
```haskell
Fix :: f (Fix f) -> Fix f
```
Let's consider our original example
```haskell
data ListF a = Nil | Cons Bool a
deriving Functor
```
Its fixed point, `ListBool` is generated when we replace `a` with `ListBool`. We get
```haskell
data ListBool = Nil | Cons Bool ListBool
```
It's exactly the list of `Bool`
### Anamorphism
The commuting square that defines the terminal coalgebra can be rewritten as
This leads directly to the recursive definition of the anamorphism
```scala=
def ana[F[_]: Functor, A](coalg: Coalgebra[F, A]): A => Fix[F] = {
a => coalg.andThen(_.map(ana(coalg))).andThen(Fix.in[F])(a)
}
```
```haskell
ana :: Functor f => Coalgebra f a -> a -> Fix f
ana coa = Fix . fmap (ana coa) . coa
```
Let's go back to our original coalgebra example
```haskell
coa1 :: Int -> ListF Int
coa1 n = if n == 0
then Nil
else Cons (even n) (n - 1)
```
and apply the anamorphism to it. We start with a seed, let's say `2`. First we apply `coa1` to it. It's not zero and it is even, so we get `Cons True 1`. Then we apply `fmap (ana coa1)` to it. This will replace the `1` with the anamorphism acting on it. Again, we apply `coa1` to get `Cons False 0` and follow it with `fmap (ana coa1)`. This time the seed is zero, so the result is `Nil`.
Each application of `ana` ends with the application of `Fix`. So altogether we get
```haskell
Fix (Cons True (Fix (Cons False (Fix Nil)))
```
which is a convoluted way of representing a list of length 2 with alternating Boolean values, `[True, False]`.
In general, a seed n will produce a list of size n alternating between `True` and `False`, starting with the parity of n.
### Laziness
The functor we were using was a sum type, with one branch being a constant (like `Nil`, which is independent of `a`). Anamorphisms for such functors terminate when they hit the constant node because `fmap` leaves such nodes unchanged. But we can also apply an anamorphism to a functor with no leaf nodes. Such an anamorphism never terminates, so it creates a truly infinite data structure. In a strict language like Scala this will lead to a non-terminating program. In a lazy language, however, the elements of an infinite data structure will be evaluated on demand, only when requested.
We can implement laziness in Scala by replacing some values with functions that produce these values.
```haskell
type Lazy a = () -> a
```
This is a helper functions that turns a value into a lazy value
```haskell
lazy :: a -> Lazy a
lazy x = \() -> x
```
We can force the evaluation of a lazy value by applying it to unit
```haskell
force :: Lazy a -> a
force lz = lz ()
```
### Lazy fixed point
A fixed point of a functor can be described as a functorful of fixed points (pseudo code)
```haskell
Fix f = f (Fix f)
```
A lazy fixed point is a lazy functorful of lazy fixed points
```haskell
newtype LFix f = LFix (Lazy (f (LFix f)))
```
More explicitly, it's a function that takes the unit and returns a functorful of lazy fixpoints (which, themselves, are functions, etc.)
```haskell
newtype LFix f = LFix (() -> (f (LFix f)))
```
The constructor is a function of the type:
```haskell
LFix :: Lazy (f (LFix f)) -> LFix f
```
To peel off the constructor and get at the functorful we use the function
```haskell
unLFix :: LFix f -> f (LFix f)
unLFix (LFix lfx) = force lfx
```
Smart constructor takes a functorful of lazy fixed points and encapsulates it in a lazy fixed point
```haskell
fix :: Functor f => f (LFix f) -> LFix f
fix = LFix . lazy
```
A lazy anamorphism takes a seed and produces a lazy fixed point.
It first applies the coalgebra to get a functorful of seeds.
Then uses fmap to convert each of these seeds to a lazy fixed point.
The result is a functorful of lazy fixed points.
It then applies `fix` to encapsulate it in a lazy fixed point
```haskell
ana' :: Functor f => Coalgebra f a -> a -> LFix f
ana' coa = fix . fmap (ana' coa) . coa
```
Compare it with
```haskell
ana :: Functor f => Coalgebra f a -> a -> Fix f
ana coa = Fix . fmap (ana coa) . coa
```
Here's the example of a lazy stream. The functor has no leaf part
```haskell
data IStreamF a = IStreamF Int a
deriving Functor
type IntLst = LFix IStreamF
```
Helper function to access first and second component
```haskell
s0 :: IStreamF a -> Int
s0 (IStreamF n _) = n
```
```haskell
s1 :: IStreamF a -> a
s1 (IStreamF _ a) = a
```
Here's the coalgebra that produces the infinite stream of natural numbers
```haskell
natsCoa :: Coalgebra IStreamF Int
natsCoa n = IStreamF n (n+1)
```
Lazy stream of natural numbers starting from `n`
```haskell
natsN :: Int -> LFix IStreamF
natsN n = ana' natsCoa n
```
Accessors: head and tail of the stream
```haskell
hd :: LFix IStreamF -> Int
hd stm = s0 (unLFix stm)
```
The tail is lazy
```haskell
tl :: LFix IStreamF -> LFix IStreamF
tl stm = s1 (unLFix stm)
```
Testing: apply tail twice, then take the head
```haskell
x = hd (tl (tl (natsN 0))) -- returns 2
```
Working with infinite data structures is often more convenient. We can generate the data in one module and let different clients consume different parts of it.
For example, we can generate a stream of prime numbers using the sieve of Erathostenes. We will use the infinite stream of integers `IntList` as the carrier for our coalgebra
This is the coalgebra that takes a seed stream as `IntLst` and splits it into a pair: the head of the stream (which will always be a prime number) and the tail, with all the multiples of the head removed. Since, in the process, all multiples of the smaller numbers were removed, the head of the tail will again be a prime number.
```haskell
era :: Coalgebra IStreamF IntLst
era nl = IStreamF h (lfilter (notdiv h) t)
where h = hd nl
t = tl nl
notdiv p n = n `mod` p /= 0
```
We have to use a lazy filter to filter an infinite list
```haskell
lfilter :: (Int -> Bool) -> IntLst -> IntLst
lfilter pred nl =
if pred h
then fix $ IStreamF h (lfilter pred t)
else lfilter pred (tl nl)
where h = hd nl
t = tl nl
```
The initial seed is the list of natural numbers starting from 2 (which is a prime number)
```haskell
primes :: LFix IStreamF
primes = ana' era (natsN 2)
```
---
```scala=
def unfold[A, S](init: S)(f: (S) => Option[(A, S)]): List[A]
```
```scala=
type Coalgebra[F[_], C] = C => F[C]
```
```scala=
def ana[F[_]: Functor, A](coalg: Coalgebra[F, A]): A => Fix[F] = {
a => coalg.andThen(_.map(ana(coalg))).andThen(Fix.in[F])(a)
}
```
```scala=
def rangeCoalg: Coalgebra[ListF[Int, *], Int] = {
n => if (n <= 0) NilF() else ConsF(n, n - 1)
}
```
```scala=
ana(rangeCoalg).apply(10)
```
// O: can't come up with a good example of coalgebra for ExprF
```scala=
implicit val toExprF: Coalgebra[ExprF, Expr] =
a => a match {
case Const(x) => ConstF(x)
case Var(s) => VarF(s)
case Times(l, r) => TimesF(l, r)
case Plus(l, r) => PlusF(l, r)
}
```
https://scastie.scala-lang.org/oli-kitty/N1K2wew3SDSGNTDp17DpcQ/2
```scala=
def selectionSort[A: Order]: Coalgebra[ListF[A, *], List[A]] =
l =>
l match {
case Nil => NilF()
case xs => ConsF(xs.min, xs.diff(List(xs.min)))
}
ana(selectionSort[Int]).apply(List(2, 15, 1, 8, 9))
```
```scala=
sealed trait TreeF[A, B]
case class LeafF[A, B](a: A) extends TreeF[A, B]
case class NodeF[A, B](l: B, r: B) extends TreeF[A, B]
def split: Coalgebra[TreeF[Int, *], List[Int]] =
l => l match {
case x :: Nil => LeafF(x)
case a :: as =>
val c = partition
NodeF(c._1, c._2)
}
```
Maybe one for quicksort:
```haskell=
data TreeF a x = LeafF | NodeF a x x
-- Grow an ordered tree from list
split :: Ord a => Coalgebra (TreeF a) [a]
split [] = LeafF
split (a: as) = NodeF a l r
where (l, r) = partition (< a) as
--
combine :: Ord a => Algebra (TreeF a) [a]
combine LeafF = []
combine (NodeF a b c) = b ++ [a] ++ c
hylo :: Functor f => Algebra f a -> Coalgebra f b -> b -> a
hylo alg coa = alg . fmap (hylo alg coa) . coa
qsort :: Ord a => [a] -> [a]
qsort = hylo combine split
```
```scala=
def partition[A](l: List[A])(p: A => Boolean): (List[A], List[A]) =
l.foldRight((List.empty[A], List.empty[A]))((a, b) => select(p, a, b))
sealed trait TreeF[A, B]
case class LeafF[A, B](a: A) extends TreeF[A, B]
case class NodeF[A, B](a: A, l: B, r: B) extends TreeF[A, B]
def split: Coalgebra[TreeF[Option[Int], *], List[Int]] = {
case Nil => LeafF(None)
case x :: Nil => LeafF(Some(x))
case a :: as =>
val c = partition(as)(_ < a)
NodeF(Some(a), c._1, c._2)
}
def combine: Algebra[TreeF[Option[Int], *], List[Int]] = {
case LeafF(None) => Nil
case LeafF(Some(x)) => x :: Nil
case NodeF(Some(a), b, c) => b ::: a :: c
}
implicit def functorForTreeF[A]: Functor[TreeF[A, *]] =
new Functor[TreeF[A, *]] {
def map[B, C](fa: TreeF[A, B])(f: B => C): TreeF[A, C] = fa match {
case LeafF(x) => LeafF(x)
case NodeF(a, b, c) => NodeF(a, f(b), f(c))
}
}
def hylo[F[_]: Functor, A, B](
alg: Algebra[F, A],
coalg: Coalgebra[F, B]
): B => A = {
coalg.andThen(_.map(hylo(alg, coalg))).andThen(alg)
}
def qsort = hylo(combine, split)
qsort.apply(6 :: 1 :: 4 :: 6 :: Nil)
qsort.apply(Nil)
```
I wonder if you can implement infinite streams in Scala
```haskell=
data StreamF a x = StreamF a x
deriving Functor
coaInt :: Coalgebra (StreamF Int) Int
coaInt n = StreamF n (n + 1)
```
This is direct translation. It might have problems with lack of laziness
```scala
sealed trait StreamF[C, R]
case class ConsStreamF[C, R](head: C, tail: R) extends StreamF[C, R]
val coaInt: Coalgebra[StreamF[Int, *], Int] =
n => ConsStreamF[Int, Int] (n, n + 1)
```
This should produce an infinite stream of integers, but in Scala it would run forever
```scala
ana(coaInt).apply(0)
```
```scala=
sealed trait StreamF[A]
final case class ConsStreamF[A](h: A, iter: A => StreamF[A])
extends StreamF[A] {
lazy val t = iter(h)
}
def ints(i: Int): ConsStreamF[Int] = ConsStreamF(i, n => ConsStreamF(n + 1, ints(i).iter))
// I didn't really get what haskell code does
def coaInt: Coalgebra[StreamF[*], Int] = {
case n => ints(n)
}
```
---
This is all the Haskell code dealing with algebras and coalgebras
```haskell
newtype Fix f = Fix { unFix :: f (Fix f) }
type Coalgebra f a = a -> f a
ana :: Functor f => Coalgebra f a -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg
type Algebra f a = f a -> a
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
hylo :: Functor f => Algebra f a -> Coalgebra f b -> b -> a
hylo f g = f . fmap (hylo f g) . g
```
This is simplified. The only thing needed is to make IntStreamF a lazy functor.
```scala=
import cats.implicits._
import cats._
case class Fix[F[_]](inner: F[Fix[F]])
object Fix {
def in[F[_]](ff: F[Fix[F]]): Fix[F] = new Fix[F](ff)
def out[F[_]]: Fix[F] => F[Fix[F]] = f => f.inner
}
type Coalgebra[F[_], A] = A => F[A]
def fix[F[_]: Functor](l: F[Fix[F]]): Fix[F] = Fix.in[F](l)
def unFix[F[_]]: Fix[F] => F[Fix[F]] = lfx => lfx.inner
def ana[F[_]: Functor, A](coalg: Coalgebra[F, A]): A => Fix[F] = { a =>
coalg.andThen(_.map(ana(coalg))).andThen(fix(_))(a)
}
// Lazy evaluation
type Lazy[A] = () => A
def force[A](la: Lazy[A]) = la()
// To make f(x) lazy, use ()=>f(x)
// You can't define
// lazy a = () => a
// because it forces the evaluation of a
// Lazy stream of integers
sealed trait IntStreamF[A]
case class ConsStreamF[A](h: Int, t: Lazy[A]) extends IntStreamF[A]
implicit def functorForIntStreamF[A]: Functor[IntStreamF[*]] =
new Functor[IntStreamF[*]] {
def map[A, C](fa: IntStreamF[A])(f: A => C): IntStreamF[C] = fa match {
case ConsStreamF(head, tail) => {
ConsStreamF(head, () => f(force(tail))) // <<<< lazy!
}
}
}
def frst[A](stm: IntStreamF[A]) = stm match {
case ConsStreamF(h, _) => h
}
def scnd[A](stm: IntStreamF[A]) = stm match {
case ConsStreamF(_, t) => t
}
def natsCoa: Coalgebra[IntStreamF, Int] = { n =>
ConsStreamF(n, () => (n + 1))
}
def natsN(n: Int): Fix[IntStreamF] = {
ana(natsCoa)(functorForIntStreamF)(n)
}
def hd: Fix[IntStreamF] => Int = stm => frst(unFix(stm))
def tl: Fix[IntStreamF] => Fix[IntStreamF] = stm => force(scnd(unFix(stm)))
print (hd(tl(tl(ana(natsCoa).apply(0)))))
```
```scala=
import cats.Functor
import cats.syntax.functor._
type Lazy[A] = () => A
case class LFix[F[_]](inner: Lazy[F[LFix[F]]])
object LFix {
def in[F[_]](ff: () => F[LFix[F]]): LFix[F] = new LFix[F](ff)
def out[F[_]]: LFix[F] => F[LFix[F]] = f => f.inner()
}
class Lazify[F[_]: Functor] {
def lazyMap[B, A](fa: F[A])(f: A => B): Lazy[F[B]] = () => fa.map(f)
}
type Coalgebra[F[_], A] = A => F[A]
def ana[F[_]: Functor, A](coalg: Coalgebra[F, A]): A => LFix[F] = { a =>
val lz = new Lazify[F]()
coalg.andThen(lz.lazyMap(_)(ana(coalg))).andThen(LFix.in(_))(a)
}
sealed trait PairWithInt[A]
case class MkPair[A](h: Int, t: A) extends PairWithInt[A]
implicit def functorForPair[A]: Functor[PairWithInt[*]] =
new Functor[PairWithInt[*]] {
def map[A, C](fa: PairWithInt[A])(f: A => C): PairWithInt[C] = fa match {
case MkPair(head, tail) => {
MkPair(head, f(tail))
}
}
}
def frst[A](stm: PairWithInt[A]) = stm match {
case MkPair(h, _) => h
}
def scnd[A](stm: PairWithInt[A]) = stm match {
case MkPair(_, t) => t
}
def hd(stm: LFix[PairWithInt]) = frst(LFix.out(stm))
def tl(stm: LFix[PairWithInt]) = scnd(LFix.out(stm))
def natsCoaPair: Coalgebra[PairWithInt, Int] = { n =>
MkPair(n, n + 1)
}
print(hd(tl(tl(ana(natsCoaPair).apply(0)))))
```
Sign in with Wallet
Connect another wallet