Clojureでモナド内包表記とStateモナド

cljsbuildのcrossoversという機能を知らない所為で今まで無駄に苦労してきましたが、これでマクロが使えないという制約から解き放たれました。
万歳！cljsbuild！

マクロが使えるようになってまず一番最初にやることは何か？
もちろん、モナド内包表記の実現ですね！

HaskellのdoよりはScalaのforの方が慣れているのでこちらを採用しました。

動的型付けの言語でのモナドの実現はいくつか見てきましたが、明示的にコンテキストを指定するタイプはあまり好かないので、ClojureらしくProtocolで表現することにしました。

Monadic Protocol

通常モナドはunitとbindが実装され、モナド則

• bind f (unit x) == f x
• bind unit m == m
• あともう一個なんかあった気がする

を満たしますが、動的型付けの言語でunitを実現するのは面倒なので、モナドっぽいインターフェースを定義します。

	(defprotocol Monadic
	(fmap [m f])
	(bind [m f]))

view raw monadic.clj hosted with ❤ by GitHub

このインターフェースが実装されていれば、モナド内包表記が使えるようになります。
とてもScala的。

モナド内包表記

Lispは神の言語と皆ネタにしていますが、Lispのマクロは本当に強力です。
既存の言語にある構文の全てはLispのマクロで表現できるのではと思えるくらいです。

Clojureの標準ライブラリではパターンマッチが出来ないので、準標準ライブラリであるcontribのcore.matchを使います。

	(defmacro do-m [bindings expression]
	(match [bindings]
	[[name value]]
	`(fmap ~value (fn [~name] ~expression))
	[[name value & bindings']]
	`(bind ~value (fn [~name] (do-m ~bindings' ~expression)))))

view raw do_m.clj hosted with ❤ by GitHub

しんぷるいずべすと、MonadPlusなんて知らないのでガードは実装しません。めんどい。

このdo-mマクロがどのように展開してくれるかというと

	(do-m
	[a m
	b (f a)]
	(g a b))

view raw expand.clj hosted with ❤ by GitHub

が

(bind m (fn [a] (fmap (f a) (fn [b] (g a b)))))

view raw expanded.clj hosted with ❤ by GitHub

こんな感じになります。

実際に動かしてみます。

	user=> (defn bind [m f] (mapcat f m))
	#'user/bind
	user=> (defn fmap [m f] (map f m))
	#'user/fmap
	user=> (do-m [a [1] b [(inc a)]] (+ a b))
	(3)

view raw example.clj hosted with ❤ by GitHub

動いたー！
素敵です。

Stateモナド

私が現在製作中のアプリケーションでは、レコードを更新する関数が多数定義されています。
これは、状態をとって、新しい状態を返す関数ですが、少し問題があります。

一つ例を示します。

	(defrecord Cursor [x y])
	(defn right [n cursor]
	(assoc cursor :x (+ (:x cursor) n)))
	(defn down [n cursor]
	(assoc cursor :y (+ (:y cursor) n)))

view raw cursor.clj hosted with ❤ by GitHub

このような関数が定義されていた時、右下へ移動する関数を定義するのに->>マクロを使い、手続き的に書くことができます。

	(defn right-down [n cursor]
	(->> cursor
	(right n)
	(down n)))

view raw right_down.clj hosted with ❤ by GitHub

しかし、このrightでの計算結果、つまりxを使う関数を定義する時、コードはこのようになります。

	(defn square [n cursor]
	(let [cursor' (right n cursor)]
	(down (:x cursor') cursor')))

view raw square.clj hosted with ❤ by GitHub

このパターンが関数内で頻出する場合、一時的なcursorの状態を保存する為の変数が増えてしまいます。
さらに、この場合はxを取得するコストは微々たるものですが、フィールドの取得に複雑なロジックを用いたり、計算値が状態の更新に間接的に使われるだけで、レコードからは取得できない場合があります。

新しい状態だけを返すのではなく、計算値とのペアで返せばこのパターンを解決できます。

	(defn right' [n cursor]
	(let [x (+ (:x cursor) n)]
	[(assoc cursor :x x) x]))

view raw right.clj hosted with ❤ by GitHub

しかし、->>マクロのようにネストせずに書けるわけではありません。

そこでStateモナドの出番です！（導入長い！

Stateモナドは状態を取り、新しい状態と計算値のペアで返す関数に対してモナドを定義したものです。

先ほど定義したMonadicをStateに実装してみます。

	(defrecord State [f]
	Monadic
	(fmap [s g]
	(State. (fn [s]
	(let [[s' a] (f s)]
	[s' (g a)]))))
	(bind [s g]
	(State. (fn [s]
	(let [[s' a] (f s)]
	((:f (g a)) s'))))))

view raw state.clj hosted with ❤ by GitHub

right, down関数をStateで定義してみます。

	(defn right [n]
	(State. (fn [cursor]
	(let [x (+ (:x cursor) n)]
	[(assoc cursor :x x) x]))))
	(defn down [n]
	(State. (fn [cursor]
	(let [y (+ (:y cursor) n)]
	[(assoc cursor :y y) y]))))

view raw state_function.clj hosted with ❤ by GitHub

この時、square関数はdo-mを使って以下のように定義できます。

	(defn square [n]
	(do-m [x (right n)
	s (down x)]
	s))

view raw state_square.clj hosted with ❤ by GitHub

ヤッター！

関数の合成が手続き的に書けますね。

まとめ

マクロ強力。Stateモナド美しい。

本当はFreeモナド使おうと思ったけどStateモナドの素晴らしさを伝えたかったので控えました。

これから70個近い関数をStaeモナドに書き換える作業が待ってます。
Freeモナドの資料も作らなきゃですね。
私の代わりに大学のC言語の課題をやってくれるといいと思います。