Just $ A sandbox

プログラミングと計算機科学とかわいさ

foldって難しくないですか

foldって難しい、というか書きづらくて読みづらくないですか、と思った話を書きます(そういう感じの話題でTLが盛り上がってたので)

以下、foldをrecursion schemeの観点から理解していることは前提とします

foldをかく

foldを書きたい

foldを書こうと思う場合は自分の場合は明白で、可換monoid積で畳むときは必ずfoldで書きます

sum = foldl (+) 0

これは入力と出力の型が一致していて細かいことを考えなくて良いし、何しているのか見れば分かるし、畳み込み感があっていい感じだし文句はない

ただこういうのは得てしてすでに欲しい関数が定義されてたりする

foldを書きたい??

これがアキュムレータ付き再帰をしたい場合になると若干微妙で、

f xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (x @@ acc)

-- ↑これが
-- ↓こうなる

f = foldl (@@) 0

上が下になるわけですが、下の方が見やすくていいやんけ、と思うじゃないですか? しかし下をパッと書くためには困ったことにfoldlの第一引数の型を暗記している必要があるので私はググるコンパイラがある場面でしか自信を持って下は書けません。

もちろん上より下の方が「良い」コードであることは明白ですが、悪いコードの方が圧倒的に自信を持って書けるのなんかおかしくないかって思いますね。

foldを書きたくない

畳み込み関数がより複雑になる可能性のあるケースでは自分はもうfoldは使いません。それが永久に修正されない、あるいは計算量を保証したいとかでなければもう再帰でいいと思っています。

そもそもこれ以上複雑なケースの場合は自分は一旦再帰の形を経由してしかfoldの処理を理解できないので、わざわざそれを頭の中でやるくらいならおとなしくコードに書けばよいのではないかという気持ちになるからです。

f = go where
  go [] = a0
  go (x:xs) = (なんかめっちゃ複雑な式) $ go xs

-- ↑元の形
-- ↓アキュムレータで書き直す

f xs = go xs b0 where
  go [] acc = acc
  go (x:xs) acc = go xs (さらに複雑な式 x acc)

-- ↓foldで書き直す

f = foldl (さらに複雑な式) b0

例えば一般に何も考えていない時は一番上の書き方をしていて、それをfoldに変えようとすると一旦アキュムレータを使う形に変える必要があります

というわけで真ん中の再帰の形を経由してから一番下に変えるわけですが、一番上から一番下には自分は脳内だけでは変換できません。(脳内ワーキングメモリー足りない人類なので)

そもそも一番下のコードを読むときにも脳内で真ん中の形に展開しないと自分は読めないので、常に真ん中経由なら真ん中でよくないか?ってなるし、計算量とか気にしないならむしろ一番上でいいでしょって思うわけです

この辺は好みや脳内ワーキングメモリーとの相談になりますがプログラムを書く際に極限まで脳みそを使いたくない自分のような人間はこういうケースではまずfoldを使いません。

また、一番上から真ん中は比較的簡単に修正可能ですが、再帰部を色々いじる可能性がある場合も一番下の式で再帰部の形をごりっと書き換えたりするのはかなり大変なので、あとで修正が入りそうな関数も敢えてfoldつかわなかったりします

foldは何がしんどいか

個人的にはこういうことだと思ってる。

foldのつらみを緩和

さて上の3つの問題は例えばこんなふうに書けると割と楽だと思います。

fold {nil: g0} {cons(x): \acc -> gn x acc} xs

まぁ当然タイプ数が増えるわけですが、しかしfoldの引数とnil,consのデータコンストラクタとの対応が見えやすいのでわかりやすいよね? しかもこれなら一般の代数的データ型に対していい感じのsyntaxが提供できるし!(その場合foldという名前はいかがなものかと思うけれど)

しかし当然Haskellではこんなsyntaxはないのでどうしようもないけれど…じゃあ妥協してこういうのでどうかな

instance TaglessList b where
  nil = acc0
  cons = \x acc -> gn x acc

おっ…これならまだ…ってお前tagless finalやんけ!!!

こんな面倒なことするくらいなら素直にfoldでよくないか

ここまで読んだ上でなお「こんな面倒なことするくらいなら素直にfoldでよくないか」と言えるのは多分脳内ワーキングメモリーが有り余ってる人なのでメモリー分けて欲しい

まとめ

  • fold難しい
  • 避けたいし再帰で書きたいけどパフォーマンス上の問題やらを引き起こす可能性が高まるかもしれないことは常に意識しておくべき
  • Haskell(に限らず大体どの言語もだけど)のsyntaxが悪い説もまぁある
  • tagless finalは便利(ただしこれだけだとリストリテラルで表現されたデータは手に入らないので使うときは注意)
  • 頑張って慣れていきましょう