初めまして一瀬です。
私が今回アドベント・カレンダーに参加したのは 実用 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)
だれかお暇な人がいましたらデバッグとかしてほしいです。