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

最近、Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire（以下、バナナ論文）を読んで、hylomorphism の定義を Scalaに書き下したりしてみたが、Wikipediaの該当記事によると「リストに同型」な再帰だけでなく、フィボナッチ数のような「非線形な呼び出しツリー」を形成する再帰でもいけるとある¹。

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

hylomorphism とは

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

出発点

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

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 のような二股に分かれる再帰には利用できない

fibonacci :: Integer -> Integer
 fibonacci n
   | n == 0 = 0
   | n == 1 = 1
   | n > 1 = fibonacci (n - 2) + fibonacci (n - 1)

共通部分を見つけて抽象度を高めたい。

改良版

この記事をヒントにして、書き直したものが下記。

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 を作るヘルパ関数も定義した。

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を定義できる。

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に渡せば、階乗関数が得られる

> 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"を与えると、計算過程を文字列として取り出すこともできる。

>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を、第１要素と第２要素の両方で再帰させるように定義すると、ツリー型再帰となる。

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に渡すパラメータで、ツリー型再帰の振る舞いをカスタマイズする。

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が並ぶのがわかる。

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

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

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
Wikipedia: Hylomorphism
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
Hylomorphisms: javascript を用いた「再帰」講座の hylomorphism回。
第7回圏論勉強会動画: 後半でF代数とcatamorphismが解説されている。

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より) ↩