Recursion Schemeによるドドスコ問題の恐るべき解法

さる8月1日、計算機科学の根幹を揺るがすドドスコ問題が出題され、エンジニアたちは震撼した（意味: 面白問題が出たので、なるべくヘンテコな解法を使って己の技巧を誇示するためにエンジニアたちは競ってコードを書きはじめた）。

【問題】配列{"ドド","スコ"}からランダムに要素を標準出力し続け、『その並びが「ドドスコスコスコ」を3回繰り返したもの』に一致したときに「ラブ注入♡」と標準出力して終了するプログラムを作成せよ(配点:5点)
— ((🐑++)) (@Sheeeeepla) 2022年8月1日

そこで、関数型テクニックをなんとかねじこんだ解法を作ったのでここに示す。

import higherkindness.droste.Coalgebra
import higherkindness.droste.data.list.{ListF, ConsF, NilF}
import higherkindness.droste.scheme

val ds = () => scala.util.Random.nextInt(2)
val dss = "スコ" :: "ドド" :: Nil
val dodosukoCoalgebra = Coalgebra[ListF[Int, *], (Int, Int)] {
  case (_, 2184) => NilF
  case (b, st) => print(dss(b)); ConsF(b, (ds(), st << 1 & 4095 | b))
}
val dodosukoAnamorphism = scheme.ana(dodosukoCoalgebra)
def injectLove() = println("ラブ注入♡")

実行する:

dodosukoAnamorphism(ds() -> Nil); injectLove()

スコドドスコスコドドスコドドドドドドスコドドスコスコドドスコスコドドドドドドスコドドスコドドスコドドドドスコスコスコスコスコドドスコドドスコドドドドドドスコスコドドスコスコドドドドスコスコスコスコスコスコドドスコドドスコスコスコドドスコドドドドスコスコドドスコドドスコスコスコドドスコドドドドスコスコドドドドドドドドスコドドスコスコドドスコドドスコスコドドドドドドスコドドドドドドドドドドスコドドドドスコドドドドドドスコドドドドドドドドドドドドドドスコスコドドドドスコドドスコドドスコスコドドドドスコスコスコスコスコスコスコドドドドドドドドドドスコドドスコスコスコドドスコドドスコスコドドスコドドスコスコスコドドドドスコスコドドスコスコドドスコドドドドドドドドスコドドスコスコスコドドスコスコドドスコドドスコドドドドスコスコスコドドドドドドドドドドスコスコスコドドドドドドスコドドスコスコドドドドドドスコスコドドスコスコドドスコドドドドスコスコスコドドスコドドスコドドドドドドスコスコスコドドドドスコドドドドドドドドドドスコドドドドスコスコスコドドスコドドドドドドスコスコドドスコスコドドスコドドドドスコスコスコスコドドスコスコスコスコスコスコドドドドスコスコドドスコドドスコスコスコドドスコドドドドスコドドスコスコスコドドスコスコスコスコスコドドスコスコスコスコドドドドスコスコドドドドドドドドスコドドスコスコドドドドスコスコスコドドスコスコスコスコスコドドスコドドドドスコスコドドスコスコスコドドドドドドドドドドドドスコドドスコドドスコドドスコドドドドドドスコドドスコスコドドスコスコスコドドドドドドドドスコスコスコドドドドスコドドスコスコスコスコスコスコスコドドドドスコドドスコスコスコスコドドドドスコスコスコドドスコスコドドスコドドスコスコスコスコスコスコスコスコドドドドドドスコドドスコスコドドドドスコドドスコスコドドスコスコスコスコドドドドドドスコドドスコドドドドドドスコドドスコドドスコスコスコスコドドドドドドスコドドスコドドドドドドスコドドドドスコスコスコドドスコスコスコドドドドスコドドスコスコドドスコスコスコドドドドスコドドドドスコドドドドドドドドスコドドスコドドスコドドドドスコドドスコスコドドドドスコドドドドスコスコスコスコドドスコスコスコドドスコスコドドドドドドスコスコスコドドスコドドスコスコスコスコスコドドスコスコドドスコスコドドスコスコスコドドスコドドスコドドドドスコドドスコスコドドドドスコスコスコスコドドスコドドスコドドドドスコドドドドスコスコドドドドドドスコドドスコスコドドドドスコスコドドスコドドスコドドスコドドドドスコスコドドドドドドドドスコスコドドドドドドスコスコスコスコドドスコドドスコドドドドドドドドドドスコドドドドスコドドスコスコスコスコスコスコドドドドドドスコスコドドスコドドスコスコスコスコスコスコスコドドスコスコスコスコスコドドスコスコドドスコスコスコドドスコドドスコドドドドスコドドスコドドドドスコスコドドスコスコドドドドドドスコスコドドドドドドドドドドドドスコスコスコドドスコスコスコスコスコドドスコスコドドスコスコスコドドスコスコスコドドスコスコスコラブ注入♡

実験は成功だ！

ちなみに依存ライブラリ等のビルド設定はこの通り。

// build.sbt
val sv = "2.13.8"

addCompilerPlugin(
  "org.typelevel" % "kind-projector" % "0.13.2" cross CrossVersion.full
)

lazy val root = project
  .in(file("."))
  .settings(
    name := "recursion-scheme-exercise",
    version := "0.1.0-SNAPSHOT",
    scalaVersion := sv,
    libraryDependencies ++= Seq(
      "org.typelevel" %% "cats-core" % "2.8.0",
      "io.higherkindness" %% "droste-core" % "0.9.0"
    )
  )

javaOptions := Seq("-Xss256m")

Recursion Schemeを表現するライブラリとしてDrosteを使った。

github.com

実装解説

このドドスコアルゴリズムは、Recursion Schemeという再帰処理を抽象化した概念をうまく利用して解いている。Recursion Scheme自体の解説記事はそのうち書くとして、ドドスコアルゴリズムを構成するいくつかの要素に着目してみよう。

ドドスコアルゴリズムは、以下の要素から構成されている:

呼び出すとランダムに1または0を返す ds
スコ と ドド がこの順に格納されている dss リスト
dsを呼び出し続け、これに対応するドドもしくはスコを表示し続け、一定パターン（ドドスコスコスコドドスコスコスコドドスコスコスコ）を出力した時に生成を中止する dodosukoCoalgebra
- Coalgebraとは余代数のこと。 ドドスコ余代数 と呼ぶことにしよう。
dodosukoCoalgebra を利用し、初期状態を与えて再帰処理を担当する dodosukoAnamorphism
- Anamorphism（ana）とは、おおまかに言えば unfold を一般化してどんなデータ構造に対しても使えるようにしたもの。 ドドスコアナモーフィズム と発音する。
ラブを注入し、ラブ注入♡と画面に出力する injectLove()

この5つのコンポーネントによってドドスコアルゴリズムは動作する。

ドドスコパターンの検出

一般に、Coalgebraは実際の次の値を計算し、再帰（つまり生成処理）を続行するか、ここでデータ構築を完了するかを選択できる。そしてAnamorphismは得られた値を再度次々Coalgebraに送り込み、再帰の面倒な箇所だけやってくれる。

具体的に、ドドスコ余代数は、以下のようにして再帰を完了するかどうかを判定している:

ドドスコスコスコドドスコスコスコドドスコスコスコ は、ドドを0に、スコを1に割り当てることでバイナリ表現（以下、 ドドスコパターン ）にできる。これは10進数では2184
ステップごとに状態st（Int型）を更新し、次のステップにも引き継ぐ。
- stは、現在のステップで得たdsの返り値をstの一番右に挿入し、さらにドドスコパターンの幅である12ビット分の幅でマスクする
- より具体的には、stを1ビット左にシフトし、st | ds()になるようにビット和を取り、12ビット分が1になっているマスク（ドドスコマスク）でビット積を取る
- ドドスコマスク0b111111111111 は10進数では4095になる
ドドスコパターンが完成した（stがドドスコパターンになった）とき、再帰は終了する

それがこの表現の中に押し込められている:

// 最終的にList[Int]を生成する。再帰するとき、次のステップには(Int, Int)を渡す
val dodosukoCoalgebra = Coalgebra[ListF[Int, *], (Int, Int)] {
  // stが2184になったとき、ドドスコパターンが完成しているのでこれで再帰を終える
  case (_, 2184) => NilF
  // stが2184ではないとき
  // 現在の状態がドドかスコかを表示する
  // そしてドドスコパターンを完成させるために状態を更新する
  case (b, st) => print(dss(b)); ConsF(b, (ds(), st << 1 & 4095 | b))
}

このドドスコ余代数には再帰自体の処理は含まれていない。余代数では、どうデータを構築するかだけを考えれば良いようになっており、再帰自体の処理はscheme.anaに隔離されているためだ。

Recursion Schemeいろいろ

冒頭で、再帰処理を抽象化したものがRecursion Schemeだと書いた。先程使ったanaもRecursion Schemeの一員だ。anaをはじめとして、Recursion Schemeには様々な種類が存在する:

データ畳み込んでいく系 -- Algebraを使う
- cata -- foldの一般化
- para -- cata に加えて、さっきまで見てきた全てのデータを参照できる
データ構築していく系 -- Coalgebraを使う
- ana -- unfold の一般化
- apo -- ana に加えて、再帰途中で強制的に別の値を再帰結果として返すことができる
コンボ技
- hylo -- cataしてからanaする
etc...

Recursion Schemeの種類は畳み込む系と展開する系とにおおまかに分かれている。そして実際にどのような問題を解きたいかは、別途Algebra/Coalgebraで実装し、最終的に組み合わせると再帰ができる、という仕組みになっている。応用として、例えばフィボナッチ数列のような再帰的数列もRecursion Schemeの組み合わせで解くことができる（DrosteのREADMEを見てほしい）。

うっひょ～、再帰自体の処理と取り扱う問題自体とが分離されてるのチョーおもしれー！と感じた君は才能があるから以下のスライドを読もう！

nrinaudo.github.io

↑これが一番オススメだ！！！

www.doscienceto.it

https://www.lambdadays.org/static/upload/media/1519663154528176valentinkasasthese10000classesineverwrote.pdf

github.com

↑これはチートシートだ！！！

欠点

末尾再帰を考えず実装した && じゃんじゃん再帰しているので、たまにStack Overflowしてしまうことがあるが、ヒープをデカくしてごまかしている。ラブには危険が付き物だ。

また、Shortでよい場所をIntで実装している。これはコードが冗長になるのを回避したためで、Shortを使うとそれなりにメモリ効率が良くなるはずだ。

感想

ドドスコ問題を見てからというもの、Recursion Schemeで書けそうだな～ということは分かっていたものの、そのためのScalaのライブラリであるDrosteの使い方がぜんぜん分からず、手探りで勉強していたら5日も経過してしまったが、普通にDrosteを使えるようになってしまったのでまあ結果オーライだな！