Scalaz始めました & foldとfoldLeftの違い

ついにScalazを使うタイミングが来たので使ってみました。

やりたいこと

現在の口座残高と、口座に出し入れした金額のリストがある。ここから、口座残高の遷移を列挙したい。手続き的に書くと以下のようになる。

 val initialAmount = 50000
 val accountHistory = 4000 :: -3200 :: 3000 :: -4500 :: -110 :: -847 :: Nil

 var current = initialAmount
 val results = new scala.collection.mutable.ListBuffer[Int]()
 accountHistory.foreach{
   h =>
     current = current + h
     results.append(current)
 }
 println(results)
 // ListBuffer(54000, 50800, 53800, 49300, 49190, 48343)

でもこういうコードはダサいのでもはや書きたくない。一回高級車乗ったらコンパクトカーとかもう乗りたくなくなるよねーみたいなノリで。まあでも、コンパクトカーにはコンパクトカーの良さがあるけど、こういうケースでの手続き的な書き方をする良さってのは「周りの人のレベルに合わせてあげる」という、どう考えても上から目線かつ誰も幸せにならないという不思議なメリットしかないのでつまり書きたくない。

アキュームレータ

で、「前回の値を基に次回の値を計算する」という感じの処理はアキュームレータ系関数(正しい呼び方が分からない)で出来る。foldとかreduceとかですね。foldとreduceの違いは、前者が初期値を別途取るのに対して、reduceは最初の要素を初期値とみなします。で、左から演算していくのと右から演算していくのとで、foldLeftとかfoldRightとかに分かれています。んじゃあfoldとfoldLeft/Rightは何が違うの?と言うのは正直良くわからん。APIを参照するとfoldの時の実行順序は不定でnondetermisticであるとされる。

じゃあなんで分けてんの?と思ってさらに調べてみると、

GenTraversable の fold が結合法則を満たさなければならない理由

GenTraversable型の変数に入ってるあるコレクションがあって(その実態は普通のcollectionかもしれないし、parallel collectionかもしれない)、実行しようとしている畳込みの演算が結合法則を満たすものだったのならば、foldLeftではなく、foldで実行しておいたほうがもし中身がparallel collectionだった場合に並列実行されて便利!
という、あまり無さそうなシチュエーションの場合に一応便利だから、普通のcollectionとparallel collectionの共通の親に定義されているのだと思う。

という事であった。ははーん。なるほどね。

いずれにせよ、foldの順序は保障されないから結合法則を満たすときにわざわざfoldLeftするとなんか意図があるように思えてしまうので、結合法則を満たすならfold、その他の場合はfoldLeft/Rightでつかってりゃいいのかな。

で、ちょっと話しが逸れちゃったけど、foldとかreduceは名前の通り畳み込みです。出てくる値は演算結果一つです。でもここでやりたいことは要素ごとに前回の演算結果を参照しつつ、今回の演算結果を出力しつつ、次の要素に演算結果を渡してあげたいということです。

そういう関数を書きゃいいんでしょうけど、いやー、このくらいなんか標準で提供されてるでしょ。と思った。だけど結局なくて、でもScalazならできるらしくて、で、ようやくここでScalazが出てくる。

mapAccumLeft

以下を参照した。

what is proper monad or sequence comprehension to both map and carry state across?

するとScalazではmapAccumLeftというそのまま欲しい関数が提供されているらしく、これを使えば万事オッケーとのこと。んじゃあやってみよう。

 val initialAmount = 50000
 val accountHistory = 4000 :: -3200 :: 3000 :: -4500 :: -110 :: -847 :: Nil

 val result = accountHistory.mapAccumLeft(initialAmount, (p: Int, c) => (p + c, p + c))
 print(result)
 // (48343,List(54000, 50800, 53800, 49300, 49190, 48343))

うん、一行になった。p+cと二回書いてるのがちょっとアホっぽいけど、まあ前の状態に比べたらずっと良いでしょう。

しかしちょっと疑問が残るのは、なんで型推論してくれないんだろう。scalazのソースを見ると以下のようになってた。

scalaz/core/src/main/scala/scalaz/IList.scala

  // private helper for mapAccumLeft/Right below
 private[this] def mapAccum[B, C](as: IList[A])(c: C, f: (C, A) => (C, B)): (C, IList[B]) =
 as.foldLeft((c, IList.empty[B])) { case ((c, bs), a) => BFT.rightMap(f(c, a))(_ :: bs) }

 /** All of the `B`s, in order, and the final `C` acquired by a stateful left fold over `as`. */
 def mapAccumLeft[B, C](c: C, f: (C, A) => (C, B)): (C, IList[B]) =
 BFT.rightMap(mapAccum(this)(c, f))(_.reverse)

mapAccumLeftの第一引数の型はCでしょ。だったら第一引数が渡された段階で第二引数の(C, A) => (C, B)のCは分かるじゃん。…あれ、引数同士の間にしか関係が無いようなものって型推論効かないのかな。なんかそんな気がしてきた。だって引数リストって一度に評価するもんな。たぶん。頭から評価していったりしないよな。たぶん…。

Scalaの型推論が頭良すぎてなんでもできちゃうような気がしてしまう。もしくは、私の書き方が何か間違ってんのかな。

追記:型推論効くようになります。

ともかく、今日はmapAccumLeftを使いました。scalazってインポートしときゃscalazの世界のListとかにimplicit conversionしてくれるんだね。Java8のStreamみたいに何か一つ関数加えないといけないとおもってました。まあ、冷静に考えたらScala使っててそんなアホなことしないか…。

今度からscalazってとりあえずインポートしとこう。そうすればIDEが色々候補をだしてくれるから。