Hatena::Groupcadr

kozima の日記

2010-08-20

qsort を loop で

| 21:09

http://d.hatena.ne.jp/einblicker/20100820/1282269376 見たら,もっと loop の機能を振り回しつつ書けそうだなって思ったので書いてみた。

(defun qsort (list)
  (if (endp (cdr list))
      list
      (loop with piv = (car list) for i in list
        if (> piv i) collect i into higher
        else if (= piv i) collect i into equal
        else collect i into lower
        finally (return (append (qsort higher) equal (qsort lower))))))

(qsort '(3 1 355 65 432 2))
;=> (1 2 3 65 355 432)

なんだか loop には中毒性があるのかもしれないと思う今日この頃。iter を覚えたいと思いつつも放置しているのです。

2010-03-30

loop でうまく書けない件の代替案?

| 21:43

http://cadr.g.hatena.ne.jp/lkozima/20100327/1269692521 の続き。

こうやればきちんと動いてコードの見た目ももう少しそれらしくなる気がして書いてみました。

(loop for x in list and i from 0
  as y = (if (a-test-which-often-returns-false x)
             (a-very-slow-function x)
             dummy)
  unless (eql y dummy)
  collect (compute-the-result i y)
  and do (a-dirty-stuff y))

やっぱりわかりやすくはないかもしれません。

2010-03-27

loop でうまく書けないこと

| 21:22

こんなような loop が書きたいなー,と思うことが時々ありますが書けなくて悲しい。

(loop for x in list and i from 0
  if (a-test-which-often-returns-false x)
  as y = (a-very-slow-function x)
  collect (compute-the-result i y) and do (a-dirty-stuff y))

やりたいことは

  • リストの要素 x とそのインデックス i について
  • たまにしか成立しないある条件を満たすときに
  • 実行に時間のかかる計算をして
  • その結果からさらに計算して得られる値をリストに格納しつつ
  • ついでに最適化のためのごちゃごちゃした処理もする

で,自然に書くと上のようにしたくなるんですけど,as は if の後に書けないので怒られます。

しょうがないので

(loop for x in list and i from 0
  if (a-test-which-often-returns-false x)
  collect (let ((y (a-very-slow-function x)))
	    (a-dirty-stuff y)
	    (compute-the-result i y)))

とか,なんかいまいちだなーと思いながら書くわけです。

2009-05-31

気持ち悪くない仮想的 loop

| 21:34

ループ変数のふるまいと破壊的変更 - 'T - cadr group に「新しく束縛を作ったらそれらしい動作になる」という記述が。確かに、そうしてやると直感に合った動作になりますね。

そのエントリの中で、ただの変数の場合には束縛でいいけど

(loop for x on '(1 2 3 4 5 6 7 8) collect (pop (cdr x)))
;=> (2 4 6 8)

のような例だとやはりうまくいかない、というところを受けて考えました。

新しい束縛を作るのは変数の中身を破壊されて変な動作になるのを防ぐため。それだったら、この場合はリストが破壊されているのだから新しいリストを作ればいいのではないでしょうか。

(loop for x on '(1 2 3 4 5 6 7 8) collect (let ((x (copy-list x))) (pop (cdr x))))
=> (2 3 4 5 6 7 8 nil)

要するに、一般には局所的に新しい generalized variable を作ってやればいいのです。変数は generalized variable なので、最初の変数を let で束縛する例もその特別な場合だと考えられます。

しかし「じゃあ alist だったら」とか「リストの要素が配列でその中身を破壊した場合は」とか言い出すと、いたちごっこです。そういう深い場所への破壊的変更がどう処理されるのが最も直感に合うか、なんて文脈によるでしょうし。それに、いちいちリストをコピーしていたら効率が悪くてしかたがありませんね。

ということで、今回の話は実際にそうなるべきとかいう話ではなくて、そういう風になってると思って読んでも問題ないようなコードを書くと(基本的には)いいんじゃないかな、というところになりそうです。直感に反するような動作をする気持ち悪いループも書けるけど、大人だったら自重しなさいよ、というところで落ち着くんでしょう。それが Lisp らしいような気もします。

2009-05-29

loop の気持ち悪い使い方

| 23:09

なんとなく思いつきで列挙してみた。

(loop for i from 1 to 10 finally (return i))
;=> 11

;; 確か処理系依存。昔どこかで話題になったような。
(loop for i from 1 to 10 collect (lambda (x) (+ x i)) into funs
    collect i into nums
    finally (return (mapcar #'funcall funs nums)))
;=> (12 13 14 15 16 17 18 19 20 21)

;; dotimes でも同じようなことはできますけど。
(loop for i from 1 to 10 collect (incf i))
;=> (2 4 6 8 10)

(loop for x on '(1 2 3 4 5 6 7 8) collect (pop x))
;=> (1 3 5 7)