2014/08/23

Haskell風のリスト内包記法をClojureで

Clojureのリスト内包記法は, forですが, この記法は少し読みにくいように感じます.

例えば, Haskellなら
[(x, y) | x <- [1..10], y <- [2..11], odd (x * y)]
と書けるところをClojureは,
(for [x (range 1 11), y (range 2 12), :when (odd? (* x y))] [x y])
と書きます.

 どのあたりが気に入らないのかというと, 真っ先に目につくのが:whenです. Haskellは注釈なしに条件を付加しています. whenのような注釈は, Haskellに必要ありません.

 :when以外にも気に入らないところがあります. generatorです. Haskellは, 例のx<-[1..10]というかなり直感的な表記ですが, Clojureは, rangeと束縛する変数を併置するという書き方で, かなり形式張った印象があります. Clojureでも, x <- [(exp1)..(exp2)]のようにかければいいかなと思いました. 一番理想的なのは, e ∈ [1..10]ですが.

 このような注釈が必要になるのは, 動的型付け言語であるClojureでは仕方がないのかもしれないです. Haskellの場合, odd (x * y)の式は, 構文を読み込んだ後の型推論のフェーズで, 式がboolを返す式であることを認識します. 一方で, Clojureは, 構文を読んだ時点で任意の関数fが, 例えば, (f (* x y))と書かれているとして, それが条件を表すとは認識できない(というか, 決定できない)と思ったのですが...

Haskell Report 98のリスト内包記法 によれば, 次のように定義されます.
[e | True ]     = [e]
[e | q    ]     = [ e | q, True ]
[e | b, Q ]     = if b then [  e | Q ] else []
[e | p <- l, Q ]= let ok p = [  e | Q ]
                      ok _ = []
                      in concatMap ok l
[e | let decls, Q ] = let decls in [  e | Q ]
 Haskellの内包記法は, letとfilter, generatorが使えます. letは, リスト内包記法内で一時的に束縛される変数を定義する式です.<-で記述される式は, generatorと呼ばれます. generatorから生成された変数列にかけるのがfilterです. 3行目のbがfilterに相当します.

 Haskellのリスト内包記法の定義をよく見ると, 型注釈から, 式をフィルターの条件式かどうかを判定しているわけではなく, 構文的に条件式だと見ているようです. つまり, 処理系から見て, リスト内包記法の構文を読む時, :whenの注釈は必要ないのかもしれません.

 :whenは, 意味的に必要なのではなくて, 分かりやすさのために存在していると見た方がよさそうです.

 Clojureのリスト内包記法がこのような表記になっている原因は, この記法のイメージの根底にあるが, for-each構文だからでしょう. 構文の名前もforと書かれています. Pythonのリスト内包記法もforが使われていました. 一方で, Haskellの記法は, 数学で用いられる集合の内包的記法を忠実に文法に落とし込んだ印象があります.

 いずれにせよ, 上記のような特徴からClojureのリスト内包記法は直感的ではないと思いました.

 というわけで, Haskell風のリスト内包記法の構文をClojureでも使えるようにします. ここで重要なのは, すべてHaskell化するのではないということです. S式は残します. 例えば, こんな感じ.
[(x, y) | x <- (range 1 11), y <- (range 2 12), (odd? (* x y))] 
 S式でコードが書けないのは, 本末転倒です. 最初からHaskellを使えばいいだけなので.

 次のようなマクロを作りました.
user=> (lc [x | x <- (range 10), (odd? x)])
(1 3 5 7 9)
user=> (lc [[x,y] | x <- (range 10), (odd? x), let y = (* x 3)])
([1 3] [3 9] [5 15] [7 21] [9 27])
 lcはHaskell風の内包記法をとり, Clojureのforへ変換します. 表記が違うだけで, 機能的にはforそのものです.
 以下がソースコード. core.matchマクロを使っているので, 使用の際には, project.cljやleinのprofileにmatchマクロを追加する必要があります.

(use '[clojure.core.match :only (match)])

(defn throw-exception [message]
  #((throw (Exception. (str message %)))))

(defn malformed-let-in-lc [s-exp]
  ((throw-exception "malformed let in list comprehension : ") s-exp))

(defn malformed-generator-in-lc [s-exp]
  ((throw-exception "malformed generator in list comprehension : ") s-exp))

(defn malformed-lc [s-exp]
  ((throw-exception "malformed list comprehension : ") s-exp))

(defn lc-tail->for [tail-exps converted]
  (let [top (first tail-exps)]
    (cond
     (empty? tail-exps) converted
     ;; let
     (= top 'let)
      (match tail-exps
             ['let var-name '= exp & rest-of-tail]
             (lc-tail->for
              rest-of-tail
              (concat converted [:let [var-name exp]]))
             a (malformed-let-in-lc a))
     ;; generator
     (and (symbol? top) (= '<- (second tail-exps)))
      (match tail-exps
             [var-name '<- generator & rest-of-tail]
             (lc-tail->for
              rest-of-tail
              (concat converted [var-name generator]))
             a (malformed-generator-in-lc a))
     ;; filter
     (list? top)
      (lc-tail->for
       (vec (rest tail-exps))
       (concat converted [:when top]))
     :else
      (malformed-lc tail-exps))))

(defmacro lc [exp]
  (match exp
         [an-element '| & list-comprehension-tail]
         `(for ~(vec (lc-tail->for list-comprehension-tail []))
            ~an-element)
         a (malformed-lc a)))
 例えば, ラマヌジャン数も求まります. (以下のS式のexpは別途用意が必要)
user=> (lc [[left [x,y,z,w]] | x <- (range 1 20),
                               y <- (range 1 20),
                               z <- (range 1 20),
                               w <- (range 1 20),
                               let left = (+ (exp x 3) (exp y 3)),
                               let right = (+ (exp z 3) (exp w 3)),
                               (= left right) (not= x y) (not= y z)
                               (not= z w) (not= x z) (not= x w) (not= y w)])
([1729 [1 12 9 10]] [1729 [1 12 10 9]] [4104 [2 16 9 15]] [4104 [2 16 15 9]] [1729 [9 10 1 12]] [1729 [9 10 12 1]] [4104 [9 15 2 16]] [4104 [9 15 16 2]] [1729 [10 9 1 12]] [1729 [10 9 12 1]] [1729 [12 1 9 10]] [1729 [12 1 10 9]] [4104 [15 9 2 16]] [4104 [15 9 16 2]] [4104 [16 2 9 15]] [4104 [16 2 15 9]])

 元のClojureのforよりは見やすくなったと信じています. 特に空白を表すカンマが適当なところで, 区切りを明確に表現して丁度いい感じになりました. しかし, lcが邪魔ですね.

 リードマクロで#[x| ...]のように記述できれば理想的なのですが, Clojureにはリードマクロを自由に追加することはできません. (追記, 2014/10/06 :  Clojureのリーダマクロ 最近のversionでは追加されたようです.) Clojure本体のコードを弄ることで, リードマクロを拡張することはできるようなのですが, それは少しやりすぎな感じがします.

0 件のコメント :