Edited at
ClojureDay 23

実用的な話?をしたい

More than 5 years have passed since last update.

初めまして一瀬です。

私が今回アドベント・カレンダーに参加したのは 実用 Common Lispの第2章で気になる箇所があったためです。

それはCommon Lispの話なのですが、ここではClojureに読み変えて話をすすめさせてもらいます。

気になっているのは、テキストp.41の関数combine-allの動作が定義とテキスト上の動作に違いがある点です。

テキストの定義 :

(combine-all '((a) (b)) '((1) (2))) 

=> ((A 1) (B 1) (A 2) (B 2))

関数の実装は、定義にのっとっており、実際にためしたところ定義通りの動作になりました。

しかし、テキスト上の動作は次のようになっています。

(combine-all '((a) (b)) '((1) (2))) 

=> ((A 1) (A 2) (B 1) (B 2))

つまり、定義と動作が不一致を起しているのです。とても気になります。

定義の実装はテキスト上にあり正常に動作していますが、動作が正しいとして考えた場合の関数の実装がないので、ここでは、それを考えてゆきます。

まず、Common Lispのcombine-allの実装 :

(defun combine-all (xlist ylist)

"Return a list of lists formed by appending a y to an x.
E.g., (combine-all '((a) (b)) '((1) (2))) -> ((A 1) (B 1) (A 2) (B 2))."
(mappend #'(lambda (y)
(mapcar #'(lambda (x) (append x y)) xlist))
ylist))
(defun mappend (fn the-list)
"Apply fn to each element of list and append the results."
(apply #'append (mapcar fn the-list)))

これをClojureに書き直して、

(defn combine-all [xlist ylist]

(mappend (fn [y]
(map (fn [x] (concat x y)) xlist))
ylist))
(defn mappend [fn the-list]
(apply concat (map fn the-list)))

実行結果は、以下の通り、定義通りになります。

user=> (combine-all '((a) (b)) '((1) (2)))

((a 1) (b 1) (a 2) (b 2))

ところで、テキスト上の動作を再現する実装は以下のようになります。

(defn combine-all [xlist ylist]

(mappend (fn [x]
(map (fn [y] (concat x y)) ylist))
xlist))

実行結果は、以下のように、テキスト上の動作と同じになりました。

user=> (combine-all '((a) (b)) '((1) (2)))

((a 1) (a 2) (b 1) (b 2))

簡単な修正で気になる点を解消できました。

それでは皆様ラブ&ピースな年越しを

追記

関数combine-allを使っているプログラムの全体像はClojureで以下のようになります。


(def *simple-grammar*
"A grammar for a trivial subset of English."
'((sentence -> (noun-phrase verb-phrase))
(noun-phrase -> (Article Noun))
(verb-phrase -> (Verb noun-phrase))
(Article -> the a)
(Noun -> man ball woman table)
(Verb -> hit took saw liked))
)
(def *grammar*
"The grammar used by generate. Initially, this is *simple-grammar*, but we can switch to other grammars."
*simple-grammar*)

(defn rule-lhs [rule]
"The left-hand side of a rule."
(first rule))
(defn rule-rhs [rule]
"The right-hand side of a rule."
(rest (rest rule)))
(defn my-assoc [category grammar]
(cond (empty? grammar) '()
(= category (first (first grammar))) (first grammar)
:else (my-assoc category (rest grammar))))
(defn rewrites [category]
"Return a list of the possible rewrites for this category."
(rule-rhs (my-assoc category *grammar*)))
(defn combine-all [xlist ylist]
(mappend (fn [y]
(map (fn [x] (concat x y)) xlist))
ylist))
(defn mappend [fn the-list]
(apply concat (map fn the-list)))

(defn generate-all [phrase]
"Generate a list of all possible expansions of this phrase."
(cond (empty? phrase) (list '())
(list? phrase) (combine-all (generate-all (first phrase))
(generate-all (rest phrase)))
(not (empty? (rewrites phrase))) (mappend generate-all (rewrites phrase))
:else (list (list phrase))))

これは、簡単な英文の組み合わせを生成するプログラムです。

想定動作は、以下のような感じです。

(generate-all 'Article)

->((the) (a))
(generate-all 'Noun)
->((man) (ball) (woman) (table))
(generate-all 'noun-phrase)
->((a man) (the man) (a ball) (the ball) (a woman) (the woman) (a table) (the table))
(count (generate-all 'sentence))
->256

ところが、このプログラムにはバグがあって、実際の動作は以下のようになります。

user=> (generate-all 'Article)

IllegalArgumentException Don't know how to create ISeq from: clojure.lang.Symbol clojure.lang.RT.seqFrom (RT.java:505)

だれかお暇な人がいましたらデバッグとかしてほしいです。