Scala
圏論
FunctionalProgramming
関数型プログラミング

階乗とフィボナッチの両方で使えるhylomorphismを書いてみる

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

ところがバナナ論文2節の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)) }

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

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(x => hylomorphism(alg, coalg)(x)))
  • Functor: これが Consリスト型やツリー型など再帰呼び出しのかたちを決める。
  • Algebra: (c, ⨁)で規定される catamorphism。
  • Coalgebra: (g, p)で規定される anamorphism。

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 coalgenra[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), coalgenra(g, p))

Functormapで第2要素のみ再帰させており、これが階乗などのリニアな 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 を表す最初の二つの引数cfに、"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

ツリー型再帰

Functormapを、第1要素と第2要素の両方で再帰させるように定義すると、ツリー型再帰となる。

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), coalgenra(g, p))

例)フィボナッチ

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のことは一旦忘れて論文の定義を見ながら改めて書いてみると納得感があるし、他のなんとかモーフィズムとの関連もだんだんわかってくる。

リソース