階乗とフィボナッチのどちらでも使える hylomorphism

最近、[Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire](https://maartenfokkinga.github.io/utwente/mmf91m.pdf)（以下、バナナ論文）を読んで、**hylomorphism** の定義を Scalaに書き下したりしてみたが、[Wikipediaの該当記事](https://en.wikipedia.org/wiki/Hylomorphism_(computer_science))によると「リストに同型」な再帰だけでなく、フィボナッチ数のような「非線形な呼び出しツリー」を形成する再帰でもいけるとある[^for-non-linear]。

ところがバナナ論文２節の hylomorphism の定義は Consリスト型の再帰であるため、どうやら`fib(n)`は定義できないらしい。そこでもう一段階抽象度を上げて、Consリスト型でもツリー型でも両方の再帰で使える hylomorphism を書いてみた（[Gist](https://gist.github.com/yasuabe/87bfec87537800be12536db2d17966f4)）。

##hylomorphism とは
* **catamorphism**（foldr）と **anamorphsim**（unfold）を合わせたもので、リストやツリーのような中間データ構造を一旦生成・展開してから、改めてたどり直して集計するようなムダを避けられるといったメリットがある。
* バナナ論文では、簡略記法は`⟦(c,⨁),(g,p)⟧`で表され、(g,p)で`unfold`したものを、(c,⨁)で`foldr`するといった意味になる（このカッコの記号が「envelope」と呼ばれている）。後述のコード例では ⨁ を f に置き換えている。

## 出発点
バナナ論文の定義を素直に書き下すと以下のようなコードになる。

```scala
def hylomorphism[A, B, C](
    c: C, f: (B, C) => C, g: A => (B, A), p: A => Boolean)(a: A): C =
  if (p(a)) c
  else g(a) match { case (b, a2) => f(b, hylomorphism(c, f, g, p)(a2)) }
```

ただしこれでは fibonacci のような二股に分かれる再帰には利用できない

```haskell
fibonacci :: Integer -> Integer
 fibonacci n
   | n == 0 = 0
   | n == 1 = 1
   | n > 1 = fibonacci (n - 2) + fibonacci (n - 1)
```
共通部分を見つけて抽象度を高めたい。

##改良版
この[記事](https://medium.com/@JosephJnk/hylomorphisms-43a5494729b7)をヒントにして、書き直したものが下記。

```scala
type Algebra[F[_],   B] = F[B] => B
type Coalgebra[F[_], A] = A    => F[A]

def hylomorphism[F[_]: Functor, A, B](
    alg:   Algebra[F, B],
    coalg: Coalgebra[F, A])(seed: A): B =
  alg(coalg(seed) map hylomorphism(alg, coalg))
```
* **Functor**: これが Consリスト型やツリー型など再帰呼び出しのかたちを決める。
* **Algebra**: (c, ⨁)で規定される catamorphism（fold）。
* **Coalgebra**: (g, p)で規定される anamorphism（unfold）。

`map`を介して`coalg`から`alg`に渡す中間データは、`Pair = Option[(X, A)]`で表し、再帰の終端に達したことを `None` で表すようにした。また `Algebra` と `Coalgebra` を作るヘルパ関数も定義した。

```scala
type Pair[X, A] = Option[(X, A)]

def algebra[A, B, C](c: C, f: (A, B) => C)(o: Pair[A, B]): C =
  o.fold(c)(f.tupled)
def coalgebra[A, B](g: A => (B, A), p: A => Boolean)(n: A): Pair[B, A] =
  if (p(n)) None else Option(g(n))
```

## Consリスト型再帰
上述の関数群を利用すると、以下のように、Consリスト型の hylomorphism を生成する関数`consHylo`を定義できる。

```scala
implicit def consHyloFunc[X]: Functor[Pair[X, ?]] = new Functor[Pair[X, ?]] {
  override def map[A, B](fa: Pair[X, A])(f: A => B): Pair[X, B] =
    fa.map(p => (p._1, f(p._2)))
}
def consHylo[A, B, C](c: C, f: (B, C) => C)(g: A => (B, A), p: A => Boolean): A => C =
  hylomorphism[Pair[B, ?], A, C](algebra[B, C, C](c, f), coalgebra(g, p))
```
`Functor`の`map`で第２要素のみ再帰させており、これが階乗などのリニアな Consリスト的再帰を形成する。

###例）階乗
バナナ論文中の例では階乗関数`fac`が以下のように定義されている。
>fac = ⟦(1,×),(g,p)⟧
>p n = n = 0
>g(1+n) = (1+n,n)

これをそのまま`consHylo`に渡せば、階乗関数が得られる

```scala
> val fac = consHylo[Int, Int, Int](1, _ * _)(n => (n, n - 1), _ == 0)
> (0 to 5).toList.map(fac)
res0: List[Int] = List(1, 1, 2, 6, 24, 120)
```

ちなみに catamorphism を表す最初の二つの引数`c`と`f`に、`"1"`、`(r1, r2) => s"$r1 * $r2"`を与えると、計算過程を文字列として取り出すこともできる。

```scala
>consHylo[Int, Long, String]("1", (r1, r2) => s"$r1 * $r2")(n => (n, n - 1), _ == 0)(10)
res1: String = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1
```


##ツリー型再帰
`Functor`の`map`を、第１要素と第２要素の両方で再帰させるように定義すると、ツリー型再帰となる。

```scala
type MaybeTree[A] = Pair[A, A]

implicit val treeHyloFunctor: Functor[MaybeTree] = new Functor[MaybeTree] {
  override def map[A, B](fa: MaybeTree[A])(f: A => B):MaybeTree[B] =
    fa.map(p => (f(p._1), f(p._2)))
}
def treeHylo[A, C](c: C, f: (C, C) => C)(g: A => (A, A), p: A => Boolean): A => C =
  hylomorphism[MaybeTree, A, C](algebra(c, f), coalgebra(g, p))
```

###例）フィボナッチ
階乗に倣うとフィボナッチは以下のような式が書ける

>fac = ⟦(1,+),(g,p)⟧
>p n = n < 2
>g(2+n) = (1+n,n)

`treeHylo`に渡すパラメータで、ツリー型再帰の振る舞いをカスタマイズする。

```scala
val fib = treeHylo[Int, Long](1, _ + _)(x => (x - 1, x - 2), _ < 2)

> (0 to 5).toList.map(fib)
res3: List[Long] = List(1, 1, 2, 3, 5, 8)
```

動きとしてはツリーの末端要素となる「1」の個数を数えるようなものになる。試みに`c="1"`、`⨁=(l, r) => s"\$l\$r"`として計算過程を文字列として取り出してみると、`fib(n)`の数だけ1が並ぶのがわかる。

```scala
> treeHylo[Int, String]("1", (l, r) => s"$l$r")(x => (x - 1, x - 2), _ < 2)(5)
res7: String = 11111111
```

前述のとおり実際には中間ツリー全体を作ってるわけではないが、あえてツリーを取り出そうとするなら以下のようにも書ける。

```scala
sealed trait Tree
case class Leaf(a: Long) extends Tree
case class Branch[A](l: Tree, r: Tree) extends Tree

treeHylo[Int, Tree](Leaf(1), (l, r) => Branch(l, r))(x => (x - 1, x - 2), _ < 2)(4)

// res9: Tree = Branch(Branch(Branch(Leaf(1),Leaf(1)),Leaf(1)),Branch(Leaf(1),Leaf(1)))
```

##所感
- 手を動かして実装してみるとやはり理解の助けになる。hylo に限らず cata などでも、ふだん使ってる`foldr`のことは一旦忘れて、論文の定義を見ながら改めて書いてみると納得感があるし、他のなんとかモーフィズムとの関連もだんだんわかってくる。
- 階乗でもフィボナッチでも、再帰の構造のみを抽出して具体的な fold、unfold と**分離**しておくことによって、計算結果だけではなく、計算過程を表現したりするプログラムも差し替えて**合成**できるようになった。こういうところが関数型プログラミングの醍醐味の一つだとおもう。


##リソース
* [Gist](https://gist.github.com/yasuabe/87bfec87537800be12536db2d17966f4)
* [Wikipedia: Hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_(computer_science))
* [Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire](https://maartenfokkinga.github.io/utwente/mmf91m.pdf)
* [Hylomorphisms](https://medium.com/@JosephJnk/hylomorphisms-43a5494729b7): javascript を用いた「再帰」講座の hylomorphism回。
* [第7回圏論勉強会動画](https://www.youtube.com/watch?v=j3bY_djVjiQ): 後半でF代数とcatamorphismが解説されている。

[^for-non-linear]: For example, a hylomorphism may also be defined by generating a non-linear call tree which is then collapsed. An example of such a function is the function to generate the nth term of the Fibonacci sequence. ([wikipedia](https://en.wikipedia.org/wiki/Hylomorphism_(computer_science)#Trees)より)