読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

少しだけClojure 5

clojure

プログラミングClojure第2版を読みながら続き。

方針

  • 基本的に本の説明をそのままor自分の言葉に直しただけで書き直すようなことはしない
  • サンプルコードが長くて理解しづらい、練習したいなと思うものは細かく試して書いてみる
  • 読んだ時点で書かれてなかったり省略されているか、疑問に思ったことを調べて書く
  • 後から書かれていたら参照のために簡単にメモする

recurと遅延シーケンス

本の例ではletfnで使っているけど、他の使い方ではどうなんだろう?ま、だいたい大丈夫だと思うけど。

まず普通のdefn

user=> (defn yo-n [n] (when (> n 0) (println "yo!") (recur (dec n))))
#'user/yo-n
user=> (yo-n 5)
yo!
yo!
yo!
yo!
yo!
nil

次、fn

user=> ((fn [n] (when (> n 0) (println "yo!") (recur (dec n)))) 5)
yo!
yo!
yo!
yo!
yo!
nil

じゃあrecurを変数に入れてそれを関数として使ったらどうなるんだろう?

user=> (def saiki recur)

CompilerException java.lang.RuntimeException: Unable to resolve symbol: recur in this context, compiling:(/tmp/form-init6665147019104305352.clj:1:1) 

user=> (def saiki recur)

CompilerException java.lang.RuntimeException: Unable to resolve symbol: recur in this context, compiling:(/tmp/form-init6665147019104305352.clj:1:1) 

あれ、名前空間に無い?fnとかのマクロで展開されるのかな?

user=> (macroexpand '(defn yo-n [n] (when (> n 0) (println "yo!") (recur (dec n)))))
(def yo-n (clojure.core/fn ([n] (when (> n 0) (println "yo!") (recur (dec n))))))

そうでもないみたいだ。まあこんな無茶なことはしないと思うけど……

それからlazy-seq-fiboをこんな風にrecurできないかと一瞬思ったけど

(defn lazy-seq-fibo
  ([]
   (concat [0 1] (recur 0N 1N)))
  ([a b]
   (let [n (+ a b)]
     (lazy-seq
      (cons n (recur b n))))))

末尾再帰じゃないじゃん。

で、どうにかして末尾再帰に変換できないかちょっと試したけど、lazy-seqで遅延シーケンス作る限り末尾再帰にできないし、する必要も無い、のかな……?

遅延シーケンスの現実化をするときは引数と結果のペアを記録したらコールスタックに積まずにそのままループになる、ってことだろうか?とりあえず本の通り巨大なフィボナッチ数列を処理できるってことは大丈夫なんでしょう。

しかしスッキリしない。自分で遅延評価書いてみたらわかるかな。あれ、前に書いたときはどうやってたっけ?

;; delay/force
(defun make-promise (f)
  (let ((flag false) (value nil))
    (lambda ()
      (unless flag
        (set! value (f))
        (set! flag true))
      value)))

(define-macro delay (expr)
  `(make-promise (lambda () ,expr)))

(defun force (promise) (promise))

;; repeat/take
(defun take (n ds)
  (cond 
    ((eq? n 0) nil)
    (otherwise 
     (cons
      (car ds)
      (take (- n 1) (force (cdr ds)))))))

(defun repeat (x) (cons x (delay (repeat x))))

(defun naturals-from (i)
  (cons i (delay (naturals-from (+ i 1)))))

ああ、promise自体はその場で評価して終わりで、force部分が末尾再帰最適化できてれば大丈夫なのか。あとnaturals-fromはiに負なんかを与えればnaturalsじゃないじゃん。。

シーケンスの現実化

なるほど、takeも遅延シーケンスを返せばその後もいろいろ利用できるのか。今度上のコードいじろう。

で、それはいいとして、じゃあどの関数が現実化するかどうやって知るんだろう?意識しなくても、遅延シーケンスを遅延シーケンスとして扱うコードを書けば大丈夫かな?

user=> (doc take)
-------------------------
clojure.core/take
([n] [n coll])
  Returns a lazy sequence of the first n items in coll, or all items if
  there are fewer than n.  Returns a stateful transducer when
  no collection is provided.
nil

user=> (doc iterate)
-------------------------
clojure.core/iterate
([f x])
  Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effects
nil

とりえあず遅延シーケンスを返すものは上のようにReturns a lazy sequence...と書いておけばいいか。

もっと怠け者の勧め

指針としてはシーケンスライブラリ→遅延シーケンス作成→末尾再帰の順で検討しましょう、ということなんだろうけど、学習する順番なら逆の方が短くなっていく感動が得られて楽しいな。(まさにそういう書き方されているので楽しい)

コイントスのペアを数えるrecur版、こういう風に実際の値でパターンマッチできるとネストが減っていいなあと思うんだけど

(defn count-heads-pairs
  ([coll]
   (count-heads-pairs 0 coll))
  ([cnt 空のseq] cnt)
  ([cnt coll]
   (recur
    (if (and 省略) (inc cnt) cnt)
    (rest coll))))

方法あるのかな?dispatchとかpattern、matchで探したけど見当たらなかった。まあパターンマッチいろいろ書くより強力なシーケンスライブラリ使ったほうがいいのかな。

次にシーケンスを、例えば[1 2 3 4][[1 2] [2 3] [3 4]]にするby-pairsを書く……よりもその後で紹介されてるpartitionを自分で書くことに挑んでみる。partitionの説明を見ておこう。

user=> (doc partition)
-------------------------
clojure.core/partition
([n coll] [n step coll] [n step pad coll])
  Returns a lazy sequence of lists of n items each, at offsets step
  apart. If step is not supplied, defaults to n, i.e. the partitions
  do not overlap. If a pad collection is supplied, use its elements as
  necessary to complete last partition upto n items. In case there are
  not enough padding elements, return a partition with less than n items.
nil

まずサンプルコードのby-pairsを分解してみる。

(defn take-pair [coll]
  (when (next coll) (take 2 coll)))

(defn by-pairs [coll]
  (lazy-seq
   (when-let [pair (seq (take-pair coll))]
     (cons pair (by-pairs (rest coll))))))

さて、partitionをどういう順番で実装しよう?

  1. [n coll]の定義を完成させて、一般化させていく
  2. [n step pad coll]の定義を完成させて、初期値を与える

後の作業が簡単なのは2だけど、いきなりステップが大きすぎるので1から攻めてみる。

[n coll]の場合、by-pairsをnで一般化したものが必要になる。名前も変えるべきだけど、面倒なのでpairのままにする。

take-pairで残りの個数がn以上か調べなきゃいけない。ちょっと迷ったけど、調べたらnthnextというそのものが出てきた。0始まり(1つ次、2つ次)に気をつければあとは簡単だ。

(defn take-pair [n coll]
  (when (nthnext coll (dec n)) (take n coll)))

(defn by-pairs [n coll]
  (lazy-seq
   (when-let [pair (seq (take-pair n coll))]
     (cons pair (by-pairs n (rest coll))))))

(defn my-partition
  ([n coll] (by-pairs n coll)))

試してみる。

user=> (my-partition 3 (take 10 (whole-numbers)))
((1 2 3) (2 3 4) (3 4 5) (4 5 6) (5 6 7) (6 7 8) (7 8 9) (8 9 10))

user=> (my-partition 1 (take 10 (whole-numbers)))
((1) (2) (3) (4) (5) (6) (7) (8) (9) (10))

次はstep。by-pairsの最後に、(rest coll)で1つ次のペアを見ていってるけど、ここを変えれば良さそう。nthrestみたいなのがあればいい。あるかな?あった。これは(nthrest coll n)で、nが0のときcollそのもの、nが1のときはrest、nが2のとき……となる。

(defn take-pair [n coll]
  (when (nthnext coll (dec n)) (take n coll)))

(defn by-pairs [n step coll]
  (lazy-seq
   (when-let [pair (seq (take-pair n coll))]
     (cons pair (by-pairs n step (nthrest coll step))))))

(defn my-partition
  ([n coll] (by-pairs n 1 coll))
  ([n step coll] (by-pairs n step coll)))

試してみる。

user=> (my-partition 3 (take 10 (whole-numbers)))
((1 2 3) (2 3 4) (3 4 5) (4 5 6) (5 6 7) (6 7 8) (7 8 9) (8 9 10))

user=> (my-partition 3 2 (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9))

user=> (my-partition 3 3 (take 10 (whole-numbers)))
((1 2 3) (4 5 6) (7 8 9))

上手くいってるかな。

最後にpad。まだ要素が残っているけどペアのサイズを満たせないとき、これにseqが指定されていたら、満たせるように先頭から要素を取って埋める。

user=> (partition 3 2 (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9))

user=> (partition 3 2 [] (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9) (9 10))

user=> (partition 3 4 [1] (take 10 (whole-numbers)))
((1 2 3) (5 6 7) (9 10 1))

user=> (partition 3 4 [1 2] (take 10 (whole-numbers)))
((1 2 3) (5 6 7) (9 10 1))

user=> (partition 4 4 [1 2] (take 10 (whole-numbers)))
((1 2 3 4) (5 6 7 8) (9 10 1 2))

take-pairに失敗したときなので、when-letをif-letに変える。あとは、先にconcatしてtakeすればいいでしょう。

(defn take-pair [n coll]
  (when (nthnext coll (dec n)) (take n coll)))

(defn take-pad [n coll pad] (take n (concat coll pad)))

(defn by-pairs [n step pad coll]
  (lazy-seq
   (if-let [pair (seq (take-pair n coll))]
     (cons pair (by-pairs n step pad (nthrest coll step)))
     (when pad (list (take-pad n coll pad))))))

(defn my-partition
  ([n coll]          (by-pairs n 1 false coll))
  ([n step coll]     (by-pairs n step false coll))
  ([n step pad coll] (by-pairs n step pad coll)))

完成かな。試してみよう。

user=> (partition 3 2 (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9))

user=> (partition 3 2 [] (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9) (9 10))

user=> (partition 3 2 [1 2] (take 10 (whole-numbers)))
((1 2 3) (3 4 5) (5 6 7) (7 8 9) (9 10 1))

user=> (partition 4 2 [1 2] (take 10 (whole-numbers)))
((1 2 3 4) (3 4 5 6) (5 6 7 8) (7 8 9 10) (9 10 1 2))

nthnext,nthrestにだいぶん助けられた気もするけど、こうやって小さい便利関数を組み合わせるのが王道だろうし、存在を知ることができて良かったのでヨシとする。

カリー化と部分適用の違い

この本の例でようやくわかった……かな?

Haskellなんで簡単に可変長引数取れないんだ……と思ってたけどその理由もわかった。

パリティ

遅延シーケンスで練習してみよう。010101……の並びを生成して、nthで取ればいいかな。

parityってなんだ?

(量・質・価値など)同等であること,等価,等量; 同率; 同等,同格

うーん?まあ複数形にすればいいか。

(def parities (cycle [0 1]))
(defn parity [n] (nth parities (dec n)))
(defn my-odd?  [n] (= 0 (parity n)))
(defn my-even? [n] (= 1 (parity n)))

感想

長くなってきたのでここまで。

  • Lisp処理系の続き作りたくなった
  • やっぱ最初からいきなり一般化したもの作るより、徐々に一般化させていったほうがいいな
広告を非表示にする