OCamlでモナドっぽいものを作る

ライブラリの拡充と関数型言語のお勉強を兼ねて、モナドっぽいものを実装して見ました。
単純にモナドをOCamlで使いたいだけならMonad拡張を入れる方が手っ取り早いですが、あまり外部ライブラリへの依存性を入れたくないのと、OCamlの記法の中だけでどこまで出来るか試してみたかったので。
ちなみに誤解を避けるため先に断っておきますが、自分はHaskellerではありません。
以下ではモナドに関してHaskellをかなり参考にしていますが、Haskellのモナドに対する勘違いなどが含まれている可能性があります。
ご了承下さい。

擬似中置記法

OCamlでは、modは特別扱いで中置記法として定義されています。

# (mod);;
- : int -> int -> int = 
# 5 mod 3;;
- : int = 2

たとえばこの別名でremという関数を作りたくても、これを中置記法で定義することは出来ません。

# let (rem) x y = x mod y;;
Error: Syntax error

これは、中置演算子として定義できる文字列が、記号の特定の組み合わせ、もしくは予約された文字列、というふうに決められているからですね。
中置演算子として予約された文字列にはor,mod,land,lor,lxor,lsl,lsr,asrがあります。
(参考：公式マニュアルのinfix-opの項)

不動点と不動点コンビネータ

ある関数 について、 となる が存在するとき、 を の不動点といいます。
また、 に十分近い に対し、列 が に収束するとき、 は の吸引的不動点である、といいます。
(参考:Wikipedia)

吸引的不動点は、値が変化しなくなるまで関数適用を繰り返すだけなので、プログラムで簡単に書くことができます。
以下のfixは初期値xからfの吸引的不動点を求める関数です。
汎用性のため、一致検査関数はequalとして引数で取ります。

let rec fix equal f x =
  let x' = f x in
    if equal x x' then x
    else fix equal f x'

第一級モジュール

OCamlには、3.12から「第一級モジュール」の機能が加わっているらしいです。
第一級モジュールとは、第一級オブジェクトとしてモジュールが扱える、つまり変数や関数と同じように関数への受け渡しや代入操作が出来るものです。
公式マニュアル7.14 第一級のモジュールに詳しい説明があります。

let多相と値多相

先日、関数合成を使うと、無駄なletやfunを減らせていいよね、という話をしました。

let (>>) f g x = g (f x)

で、関数合成を多用していると、2引数関数に対しても合成をしたくなる局面が出てきます。
たとえば、compareを元にしてequalを作ろうと思った場合、素直なコードは以下になります。

let equal x y =
  compare x y = 

これは、「xとyをcompareして、その値が0と等しいかを検査する」という関数になります。
これをcompareと(=) 0の関数合成で書こうとするとさっきの関数合成関数ではできません。(後述するカリー化とアンカリー化を使えば出来ますが)

OCamlでSetをmapする関数

今日も今日とてOCamlでプログラムをガリガリ書いていたのですが、どうしても気になってSetをmapする関数を作って見ました。
とはいえ、さすがにSetに組み込むのは無理なので、外部で似たようなことをやるための汎用関数ですが。

let mapper folder adder empty f s =
  folder (f >> adder) s empty

こんな感じです。

F#のパイプライン演算子・関数合成をOCamlで実装

最近F#が気になっているのだけれど、F#で魅力を感じる機能の一つに、パイプライン演算子というのがあります。
これはUnixのパイプライン処理に類似するもので、値をある処理に与えて、その結果をまた別の処理に与えて……というのをかなり見やすく記述できる、というものです。
例えば、リストの各要素を2乗してから和を取る、という関数sqr_sumは、素直に書くと次の様になります。

let sqr_sum l = List.fold_left (+)  (List.map (fun x -> x * x) l)

まぁ読めなくはないですが、どこから処理されるのか一瞬迷いますよね。
もっと複雑に、リストのうち奇数であるような要素のみを取り出し、これを2乗して和を取る、なんてのを書いてみましょう。