Reversing the technical interviewの解説。
平凡な三流SE(笑)の自分には難しすぎたので、解説という体を取りつつ理解しようとしてみる。
注意事項
コードの著作権は全てオリジナル作者のものです。 何か間違いがあったら私のせいです。
LinkedList
(defn cons [h t] #(if % h t))
「ただのif文じゃん」 と言ったのは面接官だけではなかったみたいだorz
#(if % h t)は匿名関数を作るマクロで、「引数がtrueであればhを、そうでなければtを返す」関数。
consの引数はクロージャ―に包み込まれて、リストに値を保存する。
(def x (cons 1 (cons 2 nil)))
つまり、xを関数として呼び出したとき、引数がtrueであれば、xを宣言した時のconsの第一引数を返し、
そうでなければ第二引数、すなわちリストの次の(cons ...)を返す。
終端はnilで表している。
Ursula K. Le Guin アーシュラ・K・ル=グウィン
アメリカの作家。「ゲド戦記」で有名。
K言語はプログラミングのK言語と彼女の名前を掛けたのだと思われる。ゲド戦記読んだことがないので詳細情報求ム。
(defn nth [l n]
(when l (if (= 0 n)
(l true)
(recur (l false) (dec n)))))
user=> (nth (cons 1 (cons 2 nil)) 1)
2
引数lにリストを渡し、nに何番目の値が欲しいのかを渡す。
n = 0になるまで再帰的に次のリストを読み込んでいく。
recurは末尾最適化するためのClojureのイディオム。
(defn hoge [x] (if (= 0 x) x (recur (dec x))))
(defn piyo [x] (if (= 0 x) x (piyo (dec x))))
user=> (piyo 100000)
StackOverflowError clojure.lang.Numbers.equal (Numbers.java:216)
user=> (hoge 100000)
0
自身の関数名を指定すると通常のJavaのメソッド呼び出しに変換されるため、スタックオーバーフローになる。
recurを使うと末尾最適化されているのがわかる。
whenマクロを使用している理由は不明。
user=> (macroexpand '(when l (if (= 0 n) (l true) (recur (l false) (dec n)))))
(if l (do (if (= 0 n) (l true) (recur (l false) (dec n)))))
whenは(if ... (do ...))に展開されるのだが、この場合doの中身はif文一つなので特に意味はない……はず。ifが二重にネストするのを避けたのだろうか?
Pythonみたいな普通のリスト
LISPerなら副作用くらいで歯ぎしりしたりしないと思う。Haskell原理主義者ならともかく。
(defn prn-list [l]
(print "(")
(loop [l l]
(if (nil? l)
(print ")\n")
(do (print (l true))
(when (l false)
(print " "))
(recur (l false))))))
loopはrecurの再帰呼び出し先になる特殊形式。リストの先頭の(print "(")のためにわざわざlをlに束縛するという非常に気持ち悪いことをやっている。なるほど、歯ぎしりしたくなるわ。
リストがnilになるまで再帰的に(do ...)を繰り返す。
まず(print (l true))でリストの中身を取り出し表示。さらに(when (l false) ...)でリストが次の値を持っている場合、空白を出力する。
ここでもifではなくwhenを使っている理由は不明。
そして最後に、その次のリストを引数に、loopを再帰呼び出しする。
今後のご活躍をお祈り申し上げます
(defn reverse [l]
(loop [r nil, l l]
(if l
(recur (cons (l true) r) (l false))
r)))
Clojureのベクターが任意の位置でカンマ区切りできることを初めて知った……。
面構えが厳ついのでたじろいでしまうが、やっていることは普通の連結リストを再帰的に逆転させるときと同じ。
rが元のリストの次の値で、lが現在の値。最初は当然nilとhead。
(cons (l true) r)で現在の値と次の値を反転させる。
この新しいリストと、(l false)の「次のノード」を「直前のリスト、現在のリスト」として再帰呼び出しを行う。リストがnilになったところで、「直前のリスト」は反転の終わったリストになっている。
感想
すごい(小並感)