リストの内包表記

30分プログラム、その56。リストの内包表記 for Scheme。
実際は、40分ちょっとかかってたりする。

内包表記(list comprehension)って?

内包表記がこれであっているのかちょっと自身がないので詳しめに、動作解説をしてみる。
Haskellのやつと動作が違うようならツッコミ希望。

まずは、単純にリストから要素をとってくる場合は次のように書ける。

(list-of x (<- x (iota 10))) ; => (0 1 2 3 4 5 6 7 8 9)

またとってきたやつに対していろんな演算を行なうこともできる。

(list-of (* x 2) (<- x (iota 10))) ; => (0 2 4 6 8 10 12 14 16 18)
(list-of (+ x 1) (<- x (iota 10))) ; => (1 2 3 4 5 6 7 8 9 10)

複数のリストからとってくることもできる。

(list-of (list x y) (<- x '(1 2 3)) (<- y '(a b c)))
; => ((1 a) (1 b) (1 c) 
;     (2 a) (2 b) (2 c) 
;     (3 a) (3 b) (3 c))

また、条件をあたえることもできる。

(list-of x (<- x (iota 10)) (even? x)) ; => (0 2 4 6 8)
(list-of x (<- x (iota 10)) (odd? x))  ; => (1 3 5 7 9)
 
; 複数の条件も与えることができる
(list-of (list x y) (<- x (iota 5)) 
                    (<- y (iota 5)) 
                    (odd? x) 
                    (even? y))
; => ((1 0) (1 2) (1 4) 
;     (3 0) (3 2) (3 4))

また、これを使うことでクイックソートを次のように書ける。

(define (qsort xs)
  (match xs
	 ((p . xs) (append (qsort (list-of x (<- x xs) (< x p)))
			   (list p)
			   (qsort (list-of x (<- x xs) (>= x p)))))
	 (_ ())))

実装

(use srfi-1)
(use util.match)
  
(define (make-clist-clause exp body)
  (match exp
	 ;; (<- x xs)は(append-map (lambda (x) ...) xs)に
	 ;; 変形する。
	 (('<- x xs) `(append-map (lambda(,x) ,body) ,xs))
	 ;; その他のS式は、ifにする
	 ;; 空リストなら、append-mapで消える
	 (_ `(if ,exp ,body ()))))
 
(define-macro(list-of exp . exps)
  (fold-right (lambda(exp body) 
		(make-clist-clause exp body))
	      `(list ,exp) ; これが最後に実行されるやつ
	      exps))

• あんなに苦労したのに、たったの18行かよ。コメントとかを抜いたら9行だしね
• よくある『内包表記はmapとfilterで実現できます』ってのはウソじゃね?filterを使っての実現方法が全然わからない
• これ健全なマクロで実現できるのかな。できそうだけど、やりかたがわからない