Arantium Maestum

プログラミング、囲碁、読書の話題

mapの表現力

最近考えるきっかけがあったので書いておく。

一般的にmapやfoldは再帰を使って実装でき、そして再帰に比べて制約がかかっていて表現力が落ちるとされている。むしろその制約があるからこそそのコードの「何をしたくて何をしないか」という意図が明確になるところが好ましい、と。

しかしこの制約はOCamlのような多機能な言語においては「お作法」的な了解によって成り立っていることであり、mapによる繰り返し作用を他の機能と組み合わせて任意のループ的な処理を実装することができる。

その一例:

exception Done
let x = ref 0
let rec ys = 0::ys
let f _ = if !x < 10 then (print_int !x; incr x) else raise Done
let _ = try List.map f ys with
  Done -> [print_endline @@ string_of_int !x]

状態xと無限リストysと例外による制御フローraise Doneを使っている。

当然ながら処理のキモはmapに渡す関数:

let f _ = if !x < 10 then (print_int !x; incr x) else raise Done

まずポイントになるのは、let f _と引数を無視していること。mapする対象のリストysはlet rec ys = 0::ysと無限に0が続くだけなので、あくまで「必要とあれば無限ループする」ためだけに使っている。

ループで破壊的変更される状態xに対して!x < 10とチェックし、条件が満たされていなければ値を出力してから破壊的にインクリメント。条件が満たされている場合例外Doneを投げることでmap全体の処理から脱出する。この脱出の部分は例外だけじゃなくて継続なり限定継続なりalgebraic effectsなりでももちろん可。

このコードの大まかな形を維持したまま、破壊的に更新していく状態などを複雑にしていけば任意のループが表現できることは想像に難くないと思う。相互再帰的なものであっても、状態にフラグを追加してそのフラグに応じて分岐するようにすればいい。

「mapが再帰に比べて表現力が落ちる」というのは「mapに渡す関数の中で発生しうるエフェクトに意図的に制限をかける」というプログラマ側の作法を前提としたものだと言える。あるいは「純粋関数型なプログラミングにおいて、モナドなどによるエフェクトを持たないmapは再帰に比べて表現力が落ちる」とするのも正確だろう。

このような作法上の制約は実際強固なので、「純粋関数を渡したmap」が再帰に比べて意図をはっきりと表明する効果があるのは間違いない。何がその意図表明を担保しているのかについて自覚的であるのは有用だろう。