2013年5月12日日曜日

ぼくのかんがえたさいきょうのMonad Syntax in Clojure

Gistに書きました。

ぼくのかんがえたさいきょうのMonad Syntax in Clojure

タイトル通りです。

最近はClojureを書いていて、モナドがなくてもThreading Macroがあればまあいいかなと思うようになってきたのですが、

Clojureのprotocolで型クラス的な多態な関数を作る

この記事に触発されたので、なにか書いてみます。

私も前にモナド内包表記について書いていたりします。

Threading Macro

->, as->, some->, cond->などはThreading Macroと呼ばれます。

このThreading Macroはモナドの利点の1つである、手続き的に記述ができるという特徴があります。

(-> a f g)

(g (f a))

と等価です。

これはポイントフリーで記述できるという利点がある反面、途中の計算結果を変数に束縛できません。

また、->someは"計算の途中でnilが返ると計算を中断してnilを返す"というコンテキストを持った->であると考えられます。

->にコンテキストを持たせたい時には新たなマクロを定義する必要があります。

モナドはこれらの問題を解決するための構文を提供します。

モナド

動的型付き言語でdo記法を模倣する際に問題になるのが、Monadにおけるreturnですが、これはdo記法ではなく、Scalaのfor式のようなモナド内包表記を採用すればよい話しだと思っています。

さらに、ClojureにはProtocolという便利な仕組みがあるので、これを活用してモナドを定義します。

(defprotocol Functor
  (fmap [m f]))

(defprotocol Monad
  (bind [m f]))

(defprotocol MonadPlus
  (mfilter [m p]))

それっぽい名前が付いていますが、細かいことは気にしないでいきましょう。

モナド内包表記において、一番大事な機能は、bindとfmapへの展開です。

(for-m [a m] (f a))
(for-m [a m b m'] (g a b))
(for-m [a m b m' c m''] (h a b c))

はそれぞれ、

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

このように展開されます。

実装は単純です。

(defmacro for-m [[var val & exprs] expr]
  (cond (empty? exprs) `(fmap ~val (fn [~var] ~expr))
        :else `(bind ~val (fn [~var] (for-m ~exprs ~expr)))))

さらに、よくある機能として、ガードと束縛を実装します。

(for-m [a m :if (p a)] (f a))
(for-m [a m :let [x (f a)]] x)

はそれぞれ、

(fmap (mfilter m (fn [a] (p a))) (fn [a] (f a)))
(fmap (fmap m (fn [a] [a (f a)])) (fn [[a x]] x))

このように展開されます。

実装は少し複雑になりますが、clojure.core/forより遥かにシンプルなので安心してください。

(defmacro for-m [[var val & exprs] expr]
  (let [[key expr' & exprs'] exprs]	
    (cond (identical? key :if)
          `(for-m [~var (mfilter ~val (fn [~var] ~expr'))
                   ~@exprs']
                  ~expr)
          (identical? key :let)
          (let [bindings (partition 2 expr')]
            `(for-m [[~var ~@(map first bindings)]
                     (for-m [~var ~val]
                            [~var ~@(map second bindings)])
                     ~@exprs']
                    ~expr))
          (empty? exprs)
          `(fmap ~val (fn [~var] ~expr))
          :else
          `(bind ~val (fn [~var] (for-m ~exprs ~expr))))))

この実装はScalaのfor式を参考にしました。

実際に使ってみましょう。

(extend-type clojure.lang.IPersistentCollection
  Functor
  (fmap [m f] (map f m))
  Monad
  (bind [m f] (mapcat f m))
  MonadPlus
  (mfilter [m p] (filter p m)))

(assert
 (= (for-m [a (range 3) b (range 3) :if (< a b)] [a b])
    '([0 1] [0 2] [1 2])))

いい感じですね。

コンテキスト

現在はfor-mで束縛される型によってコンテキストが選択されます。

Maybeモナドを定義してみましょう。

(deftype None []
  Functor
  (fmap [m f] m)
  Monad
  (bind [m f] m)
  MonadPlus
  (mfilter [m p] m))

(deftype Some [value]
  Functor
  (fmap [m f] (Some. (f value)))
  Monad
  (bind [m f] (f value))
  MonadPlus
  (mfilter [m p] (if (p value) m (None.))))

これは以下のように使います。

(let [m {:foo 1 :bar 2}
      mget (fn [m k] (if-let [v (get m k)] (Some. v) (None.)))]
  (assert
   (= (.-value (for-m [a (mget m :foo) b (mget m :bar)] (+ a b)))
      3)))

しかし、いちいち値をモナドで包む、値を取り出すことは面倒に思えます。

そこで、コンテキストを明示的に指定できるように変更します。

モナドにおけるpointを動的束縛を用いて設定し、内包表記の中では値をモナドにpointします。

(def ^:dynamic *monad* identity)

(defn point [x] (*monad* x))

pointを定義したことによってMonadにfmapのデフォルト実装を定義することができます。

(extend-type emerald.monad.Monad
  Functor
  (fmap [m f]
    (bind m (comp point f))))

直接コンテキストを指定する時、殆ど場合はモナドは内包表記のなかでのみ必要とされるので、最終的な値はモナドから取り出すことにします。

(defprotocol Comonad
  (extract [m]))

extendがないとか気にしないでください。

for-mの実装は以下のようになります。

(defmacro for-m
  ([m exprs expr]
     `(binding [*monad* #(new ~m %)]
        (extract (for-m ~exprs ~expr))))
  ([[var val & exprs] expr]
     (let [[key expr' & exprs'] exprs]
       (cond (identical? key :if)
             `(for-m [~var (mfilter (point ~val) (fn [~var] ~expr'))
                      ~@exprs']
                     ~expr)
             (identical? key :let)
             (let [bindings (partition 2 expr')]
               `(for-m [[~var ~@(map first bindings)]
                        (for-m [~var ~val]
                               [~var ~@(map second bindings)])
                        ~@exprs']
                       ~expr))
             (empty? exprs)
             `(fmap (point ~val) (fn [~var] ~expr))
             :else
             `(bind (point ~val) (fn [~var] (for-m ~exprs ~expr)))))))

使い方はこのようになります。

(deftype Maybe [value]
  Monad
  (bind [m f] (if-not (nil? value) (f value) m))
  MonadPlus
  (mfilter [m p] (if (p value) value))
  Comonad
  (extract [m] value))

(let [m {:foo 1 :bar 2}]
  (assert
   (= (for-m Maybe [a (get m :foo) b (get m :bar)] (+ a b))
      3)))

まとめ

今回は束縛される値の型によってコンテキストを変えるパターンと明示的に指定するパターンの両方を実装したことになります。

どちらもそれぞれに利点が存在するので、必要に応じて選ぶことができるような構文になりました。

Scalaのfor式は、オブジェクトシステムが存在する言語でモナドのための構文を定義する際に参考になると思います。

今回書いたプログラムはGithubで公開しています。

view raw monad.md hosted with ❤ by GitHub

2013年4月13日土曜日

ScalaでChurch encoding

data Maybe a = Nothing | Just a
という型をekmettさんのコードを参考にChurch encodingしてみると、

newtype Maybe { runMaybe :: forall r. a -> r -> r -> r }

となります。(多分)

これをScalaで表現してみました。

import scala.language.higherKinds
import scala.language.implicitConversions
import scala.language.reflectiveCalls
trait Forall[M[_]] {
def apply[A]: M[A]
}
object Maybe {
type Maybe[A] = Forall[({ type F[R] = (A => R, => R) => R })#F]
implicit def ops[A](m: Maybe[A]) = new {
def map[B](f: A => B): Maybe[B] = bind(point[B]_ compose f)(m)
def flatMap[B](f: A => Maybe[B]): Maybe[B] = bind(f)(m)
}
def point[A](a: A): Maybe[A] =
new Forall[({ type F[R] = (A => R, => R) => R })#F] {
def apply[R]: (A => R, => R) => R = (f, r) => f(a)
}
def bind[A, B](f: A => Maybe[B])(m: Maybe[A]): Maybe[B] =
new Forall[({ type F[R] = (B => R, => R) => R })#F] {
def apply[R]: (B => R, => R) => R =
(g, r) => m[R](a => f(a)[R](g, r), r)
}
def empty[A]: Maybe[A] =
new Forall[({ type F[R] = (A => R, => R) => R })#F] {
def apply[R]: (A => R, => R) => R = (f, r) => r
}
def run[A](a: A)(m: Maybe[A]): A = m[A](x => x, a)
}
object Main extends App {
import Maybe._
def get[K, V](k: K)(m: Map[K, V]): Maybe[V] =
m get k map point[V] getOrElse empty[V]
val foobar = Map('foo -> 2, 'bar -> 3)
println(run(-1)(for {
m <- get('foo)(foobar)
n <- get('bar)(foobar)
} yield m + n))
println(run(-1)(for {
m <- get('baz)(foobar)
n <- get('bar)(foobar)
} yield m + n))
}
view raw gistfile1.scala hosted with ❤ by GitHub
とても面倒なことになってますが、ちゃんとMaybeモナドとして動作します。
Haskellだと結構綺麗に書けたりします。

Church encodingすると大抵の場合に高速化されます。
このMaybeモナドの例では、emptyをbindで合成した時に、Justの場合の処理を破棄しています。

ラムダ計算で代数的データ型を表現する方法

この記事も面白いのでぜひ読んでみて下さい。

2013年3月1日金曜日

clojure.zipを使ったHistoryの表現

from gist


clojure.zipを使ったHistoryの表現

Stackを使ったHistory

よくある履歴機能の実装として、スタックを使ったものがあります。

(defrecord History [undo redo current])

(def history (partial ->History [] []))
  • commitはcurrentに新しい値を設定します。
  • undo, redoはstackの先頭から値を取り出し、currentに設定します。
(defn commit [value {:keys [undo current] :as history}]
  (assoc history
    :current value
    :undo (conj undo current)
    :redo []))

(defn undo [{:keys [undo redo current] :as history}]
  (if-let [value (peek undo)]
    (assoc history
      :current value
      :undo (pop undo)
      :redo (conj redo current))))

(defn redo [{:keys [undo redo current] :as history}]
  (if-let [value (peek redo)]
    (assoc history
      :current value
      :undo (conj undo current)
      :redo (pop redo))))

undo, redoの操作は抽象化可能です。

(defmulti inverse identity)
(defmethod inverse :undo [_] :redo)
(defmethod inverse :redo [_] :undo)

(defn return [stack {:keys [current] :as history}]
  (if-let [value (-> history stack peek)]
    (let [stack' (inverse stack)]
      (assoc history
        :current value
        stack (-> history stack (conj current))
        stack' (-> history stack' pop)))))

(def undo (partial return :undo))
(def redo (partial return :redo))

実際の動作を覗きます。

(defn peep [f obj]
  (prn obj)
  (f obj))

(->> (history "foo")
     (commit "bar")
     (commit "baz")
     (peep undo)
     (peep undo)
     (peep redo)
     (peep redo)
     prn)

以下のような出力が得られます。

#user.History{:undo ["foo" "bar"], :redo [], :current "baz"}
#user.History{:undo ["foo"], :redo ["baz"], :current "bar"}
#user.History{:undo [], :redo ["baz" "bar"], :current "foo"}
#user.History{:undo ["foo"], :redo ["baz"], :current "bar"}
#user.History{:undo ["foo" "bar"], :redo [], :current "baz"}

実にシンプルな実装ですね。

ブラウザのGo back, Go forwardや、テキストエディタのUndo, Redoはこのような動作をするものが多いと思います。

Zipperを使ったHistory

しかし、先の実装ではcommitのたびにredoが初期化されるので、変更が消えてしまうことがあります。

(->> (history "foo")
     (commit "bar")
     undo
     (commit "baz"))
; => #user.History{:undo ["foo"], :redo [], :current "baz"}

そこで、全ての変更を残し、辿ることを可能にするため、Historyを木構造で表し、Zipperで操作します。

clojure.zip/zipper

clojure.zipはZipperを扱うためのAPIです。

Zipperの構築にはclojure.zip/zipperを使います。

この関数は少々複雑です。

Usage: (zipper branch? children make-node root)
  • branch?
    • Zipperがfocusする値がブランチかどうかを判別する関数。
  • children
    • Zipperを構成する値から子ノードのシーケンスを取り出す関数。
  • make-node
    • Zipperがfocusする値と子ノードのシーケンスからZipperを構成する値を返す関数。
  • root
    • Zipperを構成する値。

例として、clojure.zip/vector-zipとclojure.zip/seq-zipの実装を挙げます。

実際にはmetadataを付加するコードが含まれます。

(defn vector-zip [root]
  (zipper vector? seq (fn [node children] (vec children)) root))

(defn seq-zip [root]
  (zipper seq? identity (fn [node children] children) root))

clojure.zip/zipperを用いたHistoryは以下のようになります。

(require '[clojure.zip :as zip])

(defprotocol History
  (branch? [history])
  (children [history])
  (make-node [history list]))

(defrecord Change [list value]
  History
  (branch? [change] true)
  (children [change] list)
  (make-node [change list]
    (assoc change :list list)))

(def change (partial ->Change []))

(def history (comp (partial zip/zipper branch? children make-node) change))

(defn commit [value history]
  (-> history (zip/insert-child (change value)) zip/down))

動作を見てみましょう。

(defn peep [f obj]
  (-> obj zip/node prn)
  (f obj))

(->> (history "foo")
     (commit "bar")
     (commit "baz")
     (peep zip/up)
     (peep zip/up)
     (peep zip/down)
     (peep zip/down)
     zip/node
     prn)

以下のような出力が得られます。

#user.Change{:list [], :buffer "baz"}
#user.Change{:list (#user.Change{:list [], :buffer "baz"}), :buffer "bar"}
#user.Change{:list (#user.Change{:list (#user.Change{:list [], :buffer "baz"}), :buffer "bar"}), :buffer "foo"}
#user.Change{:list (#user.Change{:list [], :buffer "baz"}), :buffer "bar"}
#user.Change{:list [], :buffer "baz"}

コミットが消えてしまう問題がどのように解決されたか見てみましょう。

(-> (->> (history "foo")
         (commit "bar")
         zip/up
         (commit "baz"))
    zip/up
    zip/children)
; => (#user.Change{:list [], :buffer "baz"} #user.Change{:list [], :buffer "bar"})

変更が並行に存在することが確認できました。

雑感

clojure.zip/zipperは実際複雑。

REPLでいじりながら理解するといいかもしれません。

ZipperはListやVectorのようなシーケンスだけでなく、Treeのように深さがあるようなデータ構造も扱えます。

様々なデータ構造に適用できるclojure.zipの抽象化は新鮮でした。

view raw gistfile1.md hosted with ❤ by GitHub

2013年2月7日木曜日

Destructuringを使おう

Clojureで積極的にDestructuringを使っていこうという話です。

ListやVectorに対する再帰


例: index-of

(defn index-of [value coll]
(loop [index 0 coll coll]
(cond (empty? coll) nil
(= value (first coll)) index
:else (recur (inc index) (rest coll)))))
view raw index_of1.clj hosted with ❤ by GitHub

Destructuringを使うとこんな感じで書ける。

(defn index-of' [value coll]
(loop [index 0 [head & tail :as coll] coll]
(cond (empty? coll) nil
(= value head) index
:else (recur (inc index) tail))))
view raw index_of2.clj hosted with ❤ by GitHub

firstとrestがなくなりました。

例: end

(defn end [coll]
(if (empty? (rest coll))
(first coll)
(recur (rest coll))))
view raw end1.clj hosted with ❤ by GitHub

Destructuringは関数の引数部に直接書ける。

(defn end' [[head & tail]]
(if (empty? tail)
head
(recur tail)))
view raw end2.clj hosted with ❤ by GitHub

リスト全体を束縛する変数を省略出来ました。

MapやRecordに対するDestructuring


レコードに対する操作

(defrecord Complex [real imaginary])
view raw complex.clj hosted with ❤ by GitHub

例: abs

(defn abs [complex]
(Math/sqrt (+ (Math/pow (:real complex) 2)
(Math/pow (:imaginary complex) 2))))
view raw abs1.clj hosted with ❤ by GitHub

Destructuringを使うとこんな感じ。

(defn abs' [{:keys [real imaginary]}]
(Math/sqrt (+ (Math/pow real 2)
(Math/pow imaginary 2))))
view raw abs2.clj hosted with ❤ by GitHub

{:keys [foo bar ...]}はフィールドを列挙することでその値を束縛します。

例: add

(defn add [complex complex']
(assoc complex
:real (+ (:real complex) (:real complex'))
:imaginary (+ (:imaginary complex) (:imaginary complex'))))
view raw add1.clj hosted with ❤ by GitHub

フィールドと違った名前の変数名を付ける場合は{foo' :foo bar' :bar ...}という記法が使えます。

(defn add' [{:keys [real imaginary] :as complex}
{real' :real imaginary' :imaginary}]
(assoc complex
:real (+ real real')
:imaginary (+ imaginary imaginary')))
view raw add2.clj hosted with ❤ by GitHub

Destructuringを使うことで要素の取得、束縛を簡素にしませんか?

2013年2月2日土曜日

Clojureで継承みたいなナニカ

Clojureのdeftypeやdefrecordではinterfaceのみを実装することができます。
しかし、継承のように実装があるclassを継承したいときがあります。

例えばこんなコードがあります。

(defprotocol Sequence
(add [xs x])
(empty [xs])
(head [xs])
(tail [xs]))
(defrecord Cons [x xs]
Sequence
(add [xs x] (Cons. x xs))
(empty [xs] (Nil.))
(head [_] x)
(tail [_] xs))
(defrecord Nil []
Sequence
(add [xs x] (Cons. x xs))
(empty [xs] (Nil.))
(head [_] nil)
(tail [xs] xs))
(defrecord Wrapped [list]
Sequence
(add [xs x]
(update-in xs [:list] (partial cons x)))
(empty [xs]
(Wrapped. '()))
(head [xs]
(first list))
(tail [xs]
(update-in xs [:list] rest)))
view raw sequence.clj hosted with ❤ by GitHub

ConsとNilのaddとemptyの実装が同じです。
共通化したい。

とりあえず、addとemptyを別Protocolに。

(defprotocol Sequence
(head [xs])
(tail [xs]))
(defprotocol Adder
(add [xs x])
(empty [xs]))
view raw adder.clj hosted with ❤ by GitHub

ListというProtocolを作って、それに対するAdderを定義します。

(defprotocol List
(list [xs]))
(extend-type List
Adder
(add [xs x] (Cons. x xs))
(empty [xs] (Nil.)))
view raw list.clj hosted with ❤ by GitHub

ConsとNilに対してListを実装すれば、めでたしめでたし。

(defrecord Cons [x xs]
List
(list [xs] xs)
Sequence
(head [_] x)
(tail [_] xs))
(defrecord Nil []
List
(list [xs] xs)
Sequence
(head [_] nil)
(tail [xs] xs))
view raw cons.clj hosted with ❤ by GitHub

2013年1月29日火曜日

ClojureのKeywordはLensなのですy

春休みヤッター!
ブログの更新頻度も上げていくつもりです。

Lens


Lensはあるフィールドに対するgetterとsetterを持つ。
コードにするとこんな感じ。

(defprotocol Lens
(lget [lens object])
(lset [lens object value]))
(defrecord Rational [numer denom])
(def numer
(reify Lens
(lget [lens object]
(get object :numer))
(lset [lens object value]
(assoc object
:numer value))))
(def denom
(reify Lens
(lget [lens object]
(get object :denom))
(lset [lens object value]
(assoc object
:denom value))))
view raw lens.clj hosted with ❤ by GitHub

user> (lget numer (->Rational 1 2))
1
user> (lset denom (->Rational 1 2) 3)
#lens.Rational{:numer 1, :denom 3}
view raw lget.clj hosted with ❤ by GitHub

見てわかるとおり、lgetはgetで、lsetはassocで十分なのだ。

user> (get (->Rational 1 2) :numer)
1
user> (assoc (->Rational 1 2) :denom 3)
#lens.Rational{:numer 1, :denom 3}
view raw getassoc.clj hosted with ❤ by GitHub

Lensの特徴


getとsetがあればmodifyが定義できる。

(defn modify [lens object f]
(lset lens object (f (lget lens object))))
view raw modify.clj hosted with ❤ by GitHub

user> (modify numer (->Rational 1 2) inc)
#lens.Rational{:numer 2, :denom 2}
view raw modifynumer.clj hosted with ❤ by GitHub

Clojureにはupdate-inがある。

user> (update-in (->Rational 1 2) [:numer] inc)
#lens.Rational{:numer 2, :denom 2}
view raw updatein.clj hosted with ❤ by GitHub

Lensは合成が可能だ。

(defn compose [lens lens']
(reify Lens
(lget [this object]
(lget lens (lget lens' object)))
(lset [this object value]
(lset lens (lget lens' object) value))))
view raw compose.clj hosted with ❤ by GitHub

user> (lget (compose numer denom) (->Rational 1 (->Rational 2 3)))
2

Clojureの{get, assoc, update}-in関数は複数のKeywordをとることで、ネストしたレコードに対しても有効です。

user> (get-in (->Rational 1 (->Rational 2 3)) [:denom :numer])
2
view raw getin.clj hosted with ❤ by GitHub

LensはStateモナドと組み合わせると素敵です。
更新途中の状態を取得することは出来ないけれど、Clojureにはアローマクロが存在します。

(defn add [rational {:keys [numer denom]}]
(-> rational
(update-in [:denom] (partial * denom))
(update-in [:numer] #(+ (* % denom) (* numer (:denom rational))))))
view raw arrow.clj hosted with ❤ by GitHub

user> (add (->Rational 1 2) (->Rational 2 3))
#lens.Rational{:numer 7, :denom 6}
view raw add.clj hosted with ❤ by GitHub

KeywordがLensだということを意識すれば、Lensの考え方を応用することが出来ますね。

2012年12月21日金曜日

Konst

この記事はScalaz Advent Calendarの20日目の記事です。

ScalaにはFunction.constという常に一定の値を返す関数があります。

val one = Function.const(1)_
one(2) assert_=== 1
one("hoge") assert_=== 1
view raw const.scala hosted with ❤ by GitHub

この関数を型レベルで表したものがScalazにKonstとして定義されています。

Konst


NaturalTransformationを例にKonstを使ってみます。

new (List ~> Option) {
def apply[A](list: List[A]) = list.headOption
}
new (List ~> Konst[Int]#Apply) {
def apply[A](list: List[A]) = list.size
}
new (Konst[String]#Apply ~> Konst[Int]#Apply) {
def apply[A](string: String) = string.size
}
view raw konst.scala hosted with ❤ by GitHub

あまり使わなさそうですね!
私としてはまだScalaz6にあったPartialApplyの方が便利な気がするのですが。
まあ、型推論がうまくいかなかったり、Unapplyが新しく入ったりしたことが原因にあるのでしょうね。