いもす法をRecursion Schemeを使って実装する（Scala + Droste）

いもす法というのがある:

ようするに、多次元に累積和を拡張したもの。競技プログラミングで2次元いもす法がよく使われるらしい（筆者は競プロやらないのでよく知らない）。

そして先日Recursion Schemeについていくつか記事を書いた:

blog.3qe.us

Recursion Schemeとは、再帰のデザインパターンみたいなもので、様々ある再帰処理を整理して利用しやすくしたもの。例えばフィボナッチ配列はhistomorphismとanamorphismとのコンボで書けるね～といったことがわかる。

いもす法も一種の再帰なので、Recursion Schemeを使って書いてみることにした（競技プログラミングの観点からは、ぜんぜん遅いと思うが……）。

素朴な実装
cataで書き直す
2次元に拡張する
今後の課題

お約束として、全てのコード片には以下のimportが入っているものとして進める。

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

素朴な実装

まずは、素朴に1次元の累積和を実装する。累積和なのだから、今見ている値とこれまで見てきた値の全てを足した値との和で埋めていけばよい。過去に見た値を全部見たいからparamorphismかな～と思って適当に実装した。

// 基本的な1次元累積和をまず実装する
val l = List(0, 1, 0, 0, 1, 0, -1, 0, -1, 0)
// l: List[Int] = List(0, 1, 0, 0, 1, 0, -1, 0, -1, 0)
// 今まで見てきた値を参照したいので paramorphism を使う
val cusum1RA = RAlgebra[List[Int], ListF[Int, *], List[Int]] {
  case NilF               => Nil
  case ConsF(h, (lis, t)) => h + lis.sum :: t
}
// cusum1RA: RAlgebra[List[Int], [β$0$]ListF[Int, β$0$], List[Int]] = higherkindness.droste.GAlgebra@2ad61bae
val cusum1 = scheme.zoo.para(cusum1RA)
// cusum1: List[Int] => List[Int] = <function1>
// 再帰は順番が逆になるのでreverseする
cusum1(l.reverse)
// res0: List[Int] = List(0, 0, 1, 1, 2, 2, 1, 1, 1, 0)

Listを再帰させると、Nilになるまで潜ってから計算していくので計算順序が逆になってしまう（結果も逆になってしまっている）。

しかも、毎回sumを呼び出すので計算効率はめちゃくちゃ悪いぞ！

cataで書き直す

コードをいじっていると、そもそも直前の値はcatamorphismで得ることができることがわかった。直前の値はこれまでの和になっているはずだから、paramorphismを使う必要はなかった:

// 直前の値はConsFから取り出せることがわかったのでCataでよかった:
val cusum1A = Algebra[ListF[Int, *], List[Int]] {
  case NilF              => Nil
  case ConsF(h, Nil)     => h :: Nil
  case ConsF(h, t :: ts) => h + t :: t :: ts
}
// cusum1A: Algebra[[β$1$]ListF[Int, β$1$], List[Int]] = higherkindness.droste.GAlgebra@4afbcc29
val cusum12 = scheme.cata(cusum1A)
// cusum12: List[Int] => List[Int] = <function1>
cusum12(l.reverse)
// res1: List[Int] = List(0, 0, 1, 1, 2, 2, 1, 1, 1, 0)

過去の計算結果を得るにはhistoを使うのが教科書的な説明だが、結局cataも過去の計算結果にアクセスできた。どういうことかというと、累積和で必要なのは直近の計算結果なのだからcataで問題がない。histoは過去の計算結果全てのリストを取り出すときに使う。最終的に返したい値はスカラーだが、計算過程で過去の計算結果がほしいときなどにhistoを使うことになりそう。例えば、フィボナッチ数列を計算するときには直近の計算結果だけでは不足するのでhistoが登場する。

ところで、普通のListでは::というシンタックスシュガーが使えるけれど、ConsFにはないのだろうか？

2次元に拡張する

素朴な実装ながらも1次元いもす法が完成したので、これを2次元に拡張してみよう。

いもす法の定義によれば、2次元の場合には「軸0の方向に累積させる」「軸1の方向に累積させる」が行われる（軸が増えると累積方向も増えていく）。ナイーブな実装方法として、Listをtransposeして回転させつつ、cusum1Aを行うことで実装できる。

val l2 = List(
  List(0, 0, 0, 0, 0, 0),
  List(0, 1, 0, 0, -1, 0),
  List(0, 0, 1, 0, 0, -1),
  List(0, 0, 0, 0, 0, 0),
  List(0, -1, 0, 0, 1, 0),
  List(0, 0, -1, 0, 0, 1)
)
// l2: List[List[Int]] = List(
//   List(0, 0, 0, 0, 0, 0),
//   List(0, 1, 0, 0, -1, 0),
//   List(0, 0, 1, 0, 0, -1),
//   List(0, 0, 0, 0, 0, 0),
//   List(0, -1, 0, 0, 1, 0),
//   List(0, 0, -1, 0, 0, 1)
// )

val cusum2Naive = (lis: List[List[Int]]) => {
  val first = lis.map(l => cusum12(l.reverse).reverse)
  val second = first.transpose.map(l => cusum12(l.reverse).reverse)
  second
}
// cusum2Naive: List[List[Int]] => List[List[Int]] = <function1>
cusum2Naive(l2)
// res2: List[List[Int]] = List(
//   List(0, 0, 0, 0, 0, 0),
//   List(0, 1, 1, 1, 0, 0),
//   List(0, 1, 2, 2, 1, 0),
//   List(0, 1, 2, 2, 1, 0),
//   List(0, 0, 1, 1, 1, 0),
//   List(0, 0, 0, 0, 0, 0)
// )

素朴な実装だが、素朴に書いて動くのは素晴らしいことだと思う。

ナイーブな実装の欠点として以下が挙げられそう:

transposeのコストが発生する(O(MN))
次元がさらに上昇した場合のtransposeの実装が必要
reverseのコスト(O(N))
- 次元が増えるほどreverse回数が増えていく
そもそもListは重い
- がんばればArrayで動くようにできそう？

今後の課題

ListFのConsF(head, tail)をSuperConsF[A](head:A, tails: List[SuperListF[A, *]]) の形式にすればtransposeする必要がなくなりそう
- しかしこの構造を組立てる時間が結局かかるのでは？という気がする
Arrayをラップして Functorとして振る舞うようにすればとにかくAlgebraに放り込めるようになる？

Recursion Scheme識者の方のご意見募集中です。