Lambdaカクテル

京都在住Webエンジニアの日記です

Invite link for Scalaわいわいランド
トップ > 技術 > Recursion SchemeについてScalaのDrosteで勉強する（むずかしい理論はガン無視する）

Recursion SchemeについてScalaのDrosteで勉強する（むずかしい理論はガン無視する）

技術 scala droste

前回、ドドスコ問題を解いた。

blog.3qe.us

記事ではRecursion Scheme自体の話題や、各構成要素の子細には立ち入らなかったため、Recursion Schemeを理解するためには不十分だった。そこでこの記事では、再帰的な構造、FixとPattern Functorとの関係、Recursion Schemeを構成する要素の解説を行い、具体的にDrosteでRecursion Schemeを実演する。

また、この記事では圏論や型に関する高度な知識は取り扱わない（筆者自身それほど知識豊富ではないため）。ある程度割愛した説明を行っている箇所があってもご容赦いただきたい。

記事で使われる表現

  • F[A, *] とは、F[_, _]となるような型について1つ目の型パラメータにAを代入し、2つ目は空けたままにしておくという記法である。（型の部分適用のイメージ）
    • kind-projectorの機能である
    • 例えば、type EitherInt = Either[Int, *]したとき、EitherInt[String]するとEither[Int, String]になる

また、記事中のコードには全て以下のようなimportがあると読み替えてほしい:

import higherkindness.droste._
import higherkindness.droste.data.list._

この記事では、Drosteのバージョンとして "io.higherkindness" %% "droste-core" % "0.9.0"を使っている。

Recursion Schemeのおおまかな説明

Recursion Scheme とは、再帰的処理を抽象化し、再帰のパターンのエッセンスだけ取り出した概念のカタログ、いわば再帰のデザインパターンである。Haskellではそのままrecursion-schemeとして、ScalaではDrosteとしてライブラリ化されている。それぞれのパターンについて、catamorphism、anamorphismといった名前が付けられており、よく -morphism を取り除いたcata、anaといった名前で識別されている。

  • Recursion Schemeを使うことで、構造を畳み込んだり、構造を組み上げたりできる。

再帰的データ型とPattern Functor

Recursion Schemeによる再帰に立ち入る前に、まず再帰とは何か？という事についてデータ型の観点から見ていこう。再帰的なデータ型の再帰的な部分とそうではない部分を分離することで、再帰的処理をより簡潔に書けるようになる、というのがRecursion Schemeの起点となる発想だからである。

そもそも再帰的な処理を行いたいとき、再帰的なデータ型がそこにあることがほとんどだ。

  • e.g. リストの全ての要素について処理を行いたい => List は再帰的データ構造

そこで、再帰的データ構造をどのように構成するかを考えることで、再帰処理への理解を深めていこう。

  • Pattern FunctorとFixとがこれから導入される。
  • 再帰的な型 = Pattern FunctorとFixとの合体技 に定式化して分解できることをこれから示す。

まず再帰的なデータ型とは、型が自分自身であるような要素を含んだ型のことだといえる。例えばListについて見てみよう:

e.g. List

sealed trait List[+A]
case class Cons[A](head: A, tail: List[A]) extends List[A] // tailの型はList[A]になっている！
case object Nil extends List[Nothing]

コメントにもある通り、tailがList[A]になっていて再帰していることがわかる。つまり、Listは 再帰的なデータ型 だ。List[A]の定義にList[A]が含まれているが、これをより一般化して、List[A]を「List[A]の核となる性質」と「再帰それ自体」との2つに分解できないだろうか？

Pattern Functor: ListF

再帰のことを考えたくないので、List[A]の定義からList[A]の部分を消し去って、型パラメータに持ち上げてしまおう:

// List[A]にあらわれるList[A]を型パラメータFで置換する
sealed trait ListF[+A, +F] // 型パラメータが増えた
case class ConsF[A, F](head: A, tail: F) extends ListF[A, F]
case object NilF extends ListF[Nothing, Nothing]

見掛け上、ListFは再帰的な型ではなくなった。この、再帰する型を型パラメータとして持ち上げ、見掛け上は再帰しなくなった型のことを、元の型Listの Pattern Functor と言う*1。

そして、ListFが本来のListに戻るためには、2つ目の型パラメータにListF自身を注入してもらう必要がある:

type List[+A] = ListF[A, List[A]] // 結局再帰している

しかし、ListFにも型パラメータFが含まれているから、平たく書き下すことができないようだ。型パラメータとして受け取った型を型パラメータとして注入するような型を考えることはできるだろうか？

  • ※ListFはDrosteでは既に定義されているので、自前で定義しなくてよい

Fix

ここで、新たなデータ型Fixを導入する。Fixとは、再帰的データ型から再帰的要素だけを取り出したエッセンス的な型であり、再帰そのものの表現だと考えることができる（今回はそれ以上は立ち入らない）。

Fixは以下のように定義できる:

final case class Fix[F[_](unFix: F[Fix[F])

ここでFixのコアとなる性質を示す:

  • ある再帰的な型がF = G[F] という形に式変形できるとき、F = Fix[G]の形に置き換えられる。
  • e.g. List[A] = ListF[A, List[A]] なので、List[A] = Fix[ListF[A, *]]
    • 「ListはListFの不動点である」と表現される

Fix（の元ネタであるfix関数）についての説明をもっと知りたい人は、以下リンクを読もう:

qiita.com

（データ型としてのFixと、関数としてのfixとがあるので注意。やっていることは同じだが、レイヤーが異なる）

Pattern FunctorとFix

これまでに学んできたことにより、次のことが言える:

  • 構造と再帰が、Pattern FunctorとFixとの手によって分担された
  • 再帰的な型は、Pattern FunctorとFixとを組み合わせることで再定義できる
    • 練習してみよう！ => バイナリ木構造Treeを定義し、TreeのPattern FunctorであるTreeFを作る

Algebra / Coalgebra

再帰の事はFixに押し付けたので、我々はPattern Functorをどう処理してどのような値を返すかだけを考えることで、実は再帰的処理を実装できるようになっている。

Algebra

まずは、Pattern Functorを処理するパターン。

e.g. Listの合計値を得るには？ → ListFを構成するConsFとNilFの2パターンについて、以下のように処理すれば良い:

val sum: ListF[Int, *] => Int = {
  case NilF => 0
  case ConsF(head, tail) => head + tail
}

ここでは再帰のことが完全に忘れられていることに着目してほしい。sumの為すべきことは2つだけ、NilFなら0を返し、ConsFならheadとtailとを足して返しさえすればよいのだ。

ここでAlgebraを以下のように定義する:

  • このsumのような、Pattern Functor F[_] を使った、 F[A] => A の型を持つ関数を Algebra と呼ぶ
  • Algebraの邦訳は代数。

Coalgebra

次に、Pattern Functorを返すパターン。

e.g. 指定した自然数nから1まで下降していくリストを生成するには？ → n を場合分けして、 ListFを返せばよい:

val iota: Int => ListF[Int, *] = {
  case 0 => NilF
  case n => ConsF(n, n - 1)
}

こちらも、再帰的要素が完全に排除されていることがわかる。

ここで Coalgebra を以下のように定義する:

  • このiotaのような、Pattern Functor F[_] を使って、A => F[A]の型を持つ関数を Coalgebra と呼ぶ
  • Coalgebraの邦訳は余代数。

Tips: Projection

ここは勉強不足であまり断言できない感じの知識を書いていくコーナー。

  • ListはListFで表現できることは先程示されたが、具体的なListの値をListF`に変換する方法は示されていなかった
    • List[A] => ListF[A, List[A]] するような、Pattern Functorへと変換する関数をProjectorという
    • 一般的な用語なのか不明。教えて

Catamorphism, Anamorphism, etc.

ここで、これまでに登場したキャラクターを一覧してみよう:

  • Pattern Functor -- 再帰的データ型のひな型
  • Fix -- 再帰のエッセンス
  • Algebra / Coalgebra -- Pattern Functorいじる君

ある再帰的データがあり、そこからPattern Functorを取り出せた。そしてPattern Functorに対して処理をするコードを書くことができる。後は、「適切にFixを用いて再帰させ、Algebra / Coalgebraを動作させる」パーツさえあれば再帰処理を書くことができるようになる。そしてそのパーツこそが Recursion Scheme である。

先程説明したAlgebra / Coalgebraを使って、以下のような処理を定義できる:

  • Algebraにそれぞれの要素を渡していき、構造を畳み込む処理 -これは Catamorphism (cata)という名前が付けられている
    • foldを一般化した処理だといえる
  • Coalgebraに直前に計算された値を渡していき、構造を構築していく処理
    • これは Anamorphism (ana)という名前が付けられている
    • unfoldを一般化した処理だといえる

他にもいろいろなRecursion Schemeがあるが、ほぼ全てcataとanaのバリエーションに該当する（一部紹介）:

  • e.g. hylo: anaで構築した構造を再度cataで畳み込む
  • e.g. para: cata同様にAlgebraを使うが、今まで見てきたサブツリーも見ることができる
    • 原始再帰とも言うらしい
  • e.g. apo: DrosteではRCoalgebraという拡張されたCoalgebraを使う。
  • e.g. histo: 過去の計算結果を参照できるcata

これらのバリエーションは以下PDFで一覧できる:

github.com

Recursion SchemeにAlgebra / Coalgebraを渡すと、望みの処理をしてくれる関数が返される。

実践編

ここからは、実際にRecursion Schemeを使ってDrosteの使い方を学んでいこう。

cata: sum 関数を作る

リストの合計を得るためのsum関数を作成しよう。sumは畳み込み処理だからcataを使う。

cataはAlgebraを受け取るので、sumのためのsumAlgebraを定義しよう:

val sumAlgebra = Algebra[ListF[Int, *], Int] {
  case NilF              => 0
  case ConsF(head, tail) => head + tail
}
// sumAlgebra: Algebra[[β$0$]ListF[Int, β$0$], Int] = higherkindness.droste.GAlgebra@24f0ec18

Algebraが受け取る型パラメータは、

  1. 加工に使うPattern Functor
  2. Algebraが返す値の型

となっている。

あとはsumAlgebraをscheme.cataに与えるだけで再帰関数が完成する。

val sum = scheme.cata(sumAlgebra)
// sum: List[Int] => Int = <function1>
sum(List(1, 2, 3, 4, 5))
// res0: Int = 15

tailを再帰で渡して、その値に……といった事のいっさいをcataがやってくれるので便利だ。

ana

先頭に示した記事でもうやっているので略

para: 既に読んだ値を後から参照する

cataは「今見ている」値しか計算の対象にすることができない（Algebraに渡されない）のだが、paraを使うことで「今まで見てきた」値すべてを計算の対象にできる。

累積和を計算するcusumについて考えてみよう:

val cusumRAlgebra = RAlgebra[List[Int], ListF[Int, *], List[Int]] {
  case NilF                      => Nil
  case ConsF(head, (hist, tail)) => head + hist.sum :: tail
}
// cusumRAlgebra: RAlgebra[List[Int], [β$1$]ListF[Int, β$1$], List[Int]] = higherkindness.droste.GAlgebra@6613a45f
val cusum = scheme.zoo.para(cusumRAlgebra)
// cusum: List[Int] => List[Int] = <function1>
cusum(List(-1, 0, 0, 0, 1, 0))
// res1: List[Int] = List(0, 1, 1, 1, 1, 0)
  • ListはNil部分から走査されるので、出力の順番は末尾から先頭順になっていることに注意。
  • ちょっと特殊なrecursion schemeはhigherkindness.droste.schemeの中ではなく、higherkindness.droste.scheme.zooに入っていることに注意。

他の例はまた時間があるときに。

まとめ

  • Recursion Schemeを構成する各要素の説明を行い、簡単なサンプルを動かせた。
  • 1から書いたのと、日本語の資料がぜんぜん無かったのでめちゃくちゃ疲れた。
  • Drosteはもっとサンプルやドキュメントをちゃんとしてほしい。

参考資料

nrinaudo.github.io

これを読むとだいたいわかるようになる。

45deg.github.io

これも良い。

*1:Base Functorという名称もあるようだ

★記事をRTしてもらえると喜びます
Webアプリケーション開発関連の記事を投稿しています．読者になってみませんか？