# Recursion Scheme ## Catamorphism

Type for fixed-points of F.

$type Fix(F) ≡ In { out : F(Fix(F)) }$$cata : (F(A) → A) → Fix(F) → Acata(f) ≡ f ∘ fmap(cata(f)) ∘ out$

### Laws

Cata Eval, Cata Cancel

$cata(f) ∘ In = f ∘ fmap(cata(f))$

Cata Refl

$cata(In) = id$

Cata Fusion

$f ∘ g = h ∘ fmap(f) ⇒ f ∘ cata(g) = cata(h)$

Cata Compose

$eps : forall (x). f(x) → g(x) ⇒ cata(f) ∘ cata(In ∘ eps) = cata (f ∘ eps)$

### Example

Base type for natural numbers.

$data Fℕ(r) ≡ Z | S(r) deriving Functortype ℕ ≡ Fix(Fℕ)$$toInt : ℕ → ℤtoInt ≡ cata(\case Z → 0 S(n) → n + 1)$$zero : ℕzero ≡ In(Z)$$succ : ℕ → ℕsucc(n) ≡ In(S(n))$$add : ℕ → ℕ → ℕadd(n) ≡ cata(\case Z → n S(m) → succ(m))$$mul : ℕ → ℕ → ℕmul(n) ≡ cata(\case Z → zero S(r) → add(n)(r))$

## Anamorphism

$ana : (A → F(A)) → A → Fix(F)ana(F) ≡ In ∘ fmap(ana(F)) ∘ F$

### Laws

Ana Eval

$out ∘ ana(f) = fmap(ana(f)) ∘ f$

Ana UP (Uniqueness Property)

$out ∘ g ≡ fmap(g) ∘ f ⇒ g = ana(f)$

Ana Fusion

$f ∘ g = fmap(g) ∘ h ⇒ ana(f) ∘ g = ana(h)$

### Example

$fromInt : ℤ → ℕfromInt ≡ ana λ(n) → if(n) = 0 then Z else S(n − 1)$

## Hylomorphism

$hylo : (F(B) → B) → (A → F(A)) → A → Bhylo(f)(g) ≡ f ∘ fmap(hylo(f)(g)) ∘ g$

### Laws

Hylo Split

$hylo(f)(g) ≡ cata(f) ∘ ana(g)$

Hylo Shift

$hylo(f ∘ h)(g) ≡ hylo(f)(g ∘ h)$

Hylo Fusion (Left)

$f ∘ g = g' ∘ fmap(f) ⇒ f ∘ hylo(g)(h) = hylo(g')(h)$

Hylo Fusion (Right)

$h ∘ f = fmap(f) ∘ h' ⇒ hylo(g)(h) ∘ f = hylo(g)(h')$

### Example

Base type for list.

$data ListF(A)(r) ≡ Nil | Cons(A)(r) deriving Functortype List(A) ≡ Fix(ListF(A))$

First it expands n into [1..n] by using ana, then calculate through list using cata.

$fact : ℤ → ℤfact ≡ hylo(f)(g) where f(Nil) ≡ 1 f(Cons(A)(r)) ≡ A * r g(n) ≡ if n = 0 then Nil else Cons(n)(n − 1)$

### Fix and Base t

Data structure represented as fixed-point of a functor, and type family defining the relation between the data structure and the underlying functor.

$type family Base(t) : * → *type instance Base([A]) ≡ ListF(A)$

Recursion Schemes of Recursion

$class Functor(Base(t)) ⇒ Recursive(t) where project : t → Base(t)(t)$

Catamorphism

$cata : (Base(t)(A) → A) → t → Acata(f) ≡ f ∘ fmap(cata(f)) ∘ project$

Recursion structure of list.

$instance Recursive([A]) where project(nil) ≡ Nil project(cons(x)(xs)) ≡ Cons(x)(xs)$$length' : [A] → ℤ length' ≡ cata \case Nil → 0 (Cons(_)(r)) → r + 1$

## Folds

### Paramorphism

$para : (F(Fix(F) × A) → A) → Fix(F) → Apara(f) ≡ f ∘ fmap ((,) <*> para(f)) ∘ out$

#### Laws

Para Eval

$para(f) ∘ In = f ∘ (λ(x). fmap((x,) ∘ para(f))$

Para Fusion

$f ∘ g = h ∘ fmap (\(x, r) → (x, f(r))) ⇒ f ∘ para(g) ≡ para(h)$

#### Example

$one : ℕ one ≡ succ(zero)$$fact : ℕ → ℕ fact ≡ para \case Z → one S(n)(r) → mul(succ(n))(r)$

### Zygomorphism

$zygo : (F(B) → B) → (F(B × A) → A) → Fix(F) → Azygo(f)(g) ≡ snd ∘ cata(\(x). (f(fmap(fst)(x)), g(x)))$

### Mutumorphism

$mutu : (F(A × B) → A) → (F(A × B) → B) → Fix(F) → (A × B)mutu(f)(g) ≡ cata(\(x). (f(x), g(x)))$

Derive para from zygo.

$para = zygo(In)$

Derive zygo from mutu.

$zygo(f)(g) = snd ∘ mutu(f ∘ fmap(fst))(g)$

## Histomorphism

$data Cofree(F)(A) ≡ A :< F(Cofree(F)(A))$$extract : Cofree(F)(A) → Aextract(A :< _) ≡ A$$histo : (F(Cofree(F)(A)) → A) → Fix(F) → Ahisto(f) ≡ extract ∘ cata(λ(x). f(x) :< x)$

### Example

$fibo : ℕ → ℕ fibo ≡ histo(\case Z → one S(_ :< Z) → one S(a :< S (b :< _)) → add(a)(b))$

### Prepromorphism

$prepro : (forall(A). F(A) → F(A)) → (F(A) → A) → Fix(F) → Aprepro(h)(f) ≡ f ∘ fmap(prepro(h)(f) ∘ cata(In ∘ h)) ∘ out$

## Unfolds

### Apomorphism

$apo : (A → F(Fix(F) + A)) → A → Fix(F)apo(f) ≡ In ∘ (fmap(either(id)(apo(f)))) ∘ f$

### Futumorphism

$data Free(F)(A) ≡ Pure(A) | Free(F(Free(F)(A)))$$futu : (A → F(Free(F)(A))) → A → Fix(F)futu(f) ≡ ana(g) ∘ Pure where g(Pure(A)) ≡ f(A) g(Free(fm)) ≡ fm$

### Postpromorphism

$postpro : (forall(F)(A). F(A)) → (A → F(A)) → A → Fix(F)postpro(h)(f) ≡ In ∘ fmap(ana(h ∘ out) ∘ postpro(h)(f)) ∘ f$

## Metamorphism

Jeremy Gibbons' metamorphism

$meta : (F(A) → A) → (A → B) → (B → G(B)) → Fix(F) → Fix(G)meta(f)(g)(h) ≡ ana(h) ∘ g ∘ cata(f)$

### Chronomorphism

$chrono : (F(Cofree(F)(B)) → B) → (A → F(Free(F)(A))) → A → Bchrono(f)(g) ≡ histo(f) ∘ futu(g)$

### Dynamorphism

$dyna : (F(Cofree(F)(B)) → B) → (A → F(A)) → A → Bdyna(phi)(psi) ≡ extract ∘ hylo(ap)(psi) where ap(f) ≡ phi(f) :< f$

### Elgot Algebra

$elgot : (F(B) → B) → (A → B + F(A)) → A → Belgot(f)(g) ≡ either(id)(f ∘ fmap(elgot(f)(g))) ∘ g$

$cataM : (Traversable(F), Monad(m)) ⇒ (F(A) → m(A)) → Fix(F) → m(A)cataM ≡ cata ∘ (sequence>=>)$

### Mendler Style

$mcata : (forall(B). (B → A) → F(B) → A) → Fix(F) → Amcata(f) ≡ f(mcata(f)) ∘ out$$cata : (F(A) → A) → Fix(F) → Acata(f) ≡ mcata(λ(g). f ∘ fmap(g))$$mhisto : (forall(A). (A → B) → (A → F(A)) → F(A) → B) → Fix(F) → Bmhisto(psi) ≡ psi(mhisto(psi))(out) ∘ out$

## Generalisation

$gcata : Comonad(w) ⇒ (forall(B). F(w(B)) → w(F(B))) → (F(w(A)) → A) → Fix(F) → Agcata(dist)(f) ≡ extract ∘ c where c ≡ fmap(f) ∘ dist ∘ fmap(duplicate ∘ c) ∘ out$$distCata : F(Identity(A)) → Identity(F(A))distCata ≡ Identity ∘ fmap(runIdentity)$$cata : (F(Identity(A)) → A) → Fix(F) → Acata ≡ gcata(distCata)$$distZygo : (F(B) → B) → F(B × A) → (B, F(A))distZygo(g)(m) ≡ (g(fmap(fst)(m)), fmap(snd)(m))$$zygo : (F(B) → B) → (F(B × A) → A) → Fix(F) → Azygo(g) ≡ gcata(distZygo(g))$$distHisto : F(Cofree(F)(A)) → Cofree(F)(F(A))distHisto(fc) ≡ fmap(extract)(fc) :< fmap(\(_ :< fc') → distHisto(fc'))(fc)$$histo : (F(Cofree(F)(A)) → A) → Fix(F) → Ahisto ≡ gcata(distHisto)$