変数の有効範囲を表す用語にスコープ (scope) [*1] があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ (lexical scope)」と「ダイナミックスコープ (dynamic scope)」の 2 つに分けることができます。伝統的な Lisp はダイナミックスコープですが、Common Lisp はレキシカルスコープを採用 [*2] しています。
「クロージャ (closure)」は簡単に説明すると、評価する関数と参照可能なレキシカル変数を結びつけたものです。クロージャは関数と同じく評価することができますが、クロージャを生成するときにアクセス可能なレキシカル変数を保持しているところが異なります。参照可能なレキシカル変数の集合を「環境 (environment)」と呼ぶことがあります。
クロージャは初心者の方にとってちょっと難しい概念かもしれません。クロージャを正しく理解するポイントのひとつがレキシカル変数の有効範囲 (レキシカルスコープ) です。まず最初に、レキシカル変数のアクセスについて、詳しく説明することにしましょう。
それでは、レキシカル変数の規則を詳しく見ていきましょう。変数 X を表示する関数 foo を定義します。
(defun foo () (print x)) FOO * (foo) => エラー "The variable X is unbound."
foo には変数 X を定義していないので、foo を実行するとスペシャル変数の値を探しにいきますが、定義されていないのでエラーになります。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 にはレキシカル変数 X を定義します。この場合、foo は X の値を表示するのでしょうか。実際に試してみましょう。
(defun foo1 () (let ((x 100)) (foo))) FOO1 * (foo1) => エラー "The variable X is unbound."
エラーになりました。このように、foo1 で定義したレキシカル変数 X は、foo からアクセスすることはできません。次の図を見てください。
┌────── Lisp system ───────┐
│ │
│ X (未定義) ←──────┐ │
│ │ │
│ ┌→┌─ 関数 foo ──────┐ │ │
│ │ │ ┌──────┼─┘ │
│ │ │ (print x) │ │
│ │ │ │ │
│ │ └────────────┘ │
│ │ ┌─ 関数 foo1 ─────┐ │
│ │ │ │ │
│ │ │ ┌─let : x ───┐ │ │
│ │ │ │ │ │ │
│ └─┼─┼─ (foo) │ │ │
│ │ └────────┘ │ │
│ └────────────┘ │
│ │
└────────────────────┘
図 : レキシカルスコープ
上図では変数の有効範囲を枠で表しています。foo1 の let で定義したレキシカル変数 X は、let の枠の中でのみ有効です。枠は S 式に対応していて、この場合は (let ((x 100)) ..... ) が内側の枠になります。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠 (defun foo1 () ... ) に行き着きます。ここで変数が見つからない場合はスペシャル変数の値を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 X が定義されていないので、スペシャル変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 X にアクセスすることはできないのです。これを「レキシカルスコープ (lexical scope)」といいます。レキシカルには文脈上いう意味があり、変数が定義されている S 式の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
Common Lisp では、関数の引数や let などで定義したレキシカル変数はレキシカルスコープで扱われます。次の例を見てください。
(defun foo (a) ─────────
(let ((b 20)) ────── ↑
↑ │A:10
・・１・・ │B:20 │
│ │
(let ((c 30)) ── │ │
↑C:30 │ │
・・２・・ ↓ ↓ │
)) ────── │
│
・・３・・ ↓
) ─────────
図 : レキシカル変数の有効範囲
たとえば、(foo 10) を評価したとしましょう。引数 A には 10 がセットされますね。変数 A の値は関数 foo の全体で有効です。つまり、foo の中で変数 A にアクセスすると、その値は 10 となります。次に、let でレキシカル変数 B を定義しています。変数 B はそれを定義した let の中だけが有効です。同様にレキシカル変数 C を let で定義しています。この状態で、レキシカル変数の有効範囲はどのようになるでしょうか。
1 の位置では、レキシカル変数は A と B の 2 つが定義されていますが、C は定義されていません。この位置で A と B にアクセスすると、それぞれ 10 と 20 の値になりますが、C にアクセスすることはできません。2 の位置では 3 つのレキシカル変数 A, B, C が定義されているので、その値は 10, 20, 30 となります。
3 の位置では、レキシカル変数 B と C を定義した let の範囲外ですね。この場合、アクセスできるレキシカル変数は A だけになります。繰り返しますが、レキシカル変数はそれを定義した S 式の範囲内でのみ有効なのです。関数の引数であれば、それを定義した defun の S 式が範囲内であり、let, dotimes, dolist などの場合も同じです。
それでは、ラムダ式の場合はどうなるのでしょうか。次の例を見てください。
リスト : リストの要素を N 倍する (defun times-element (n xs) (mapcar (lambda (x) (* x n)) xs))
ラムダ式の仮引数は X だけですから、変数 N はスペシャル変数の値を探しにいくと思われるかもしれません。ところが、変数 N は関数 times-element の引数 N にアクセスするのです。これを図に示すと、次のようになります。
┌────── Lisp system ──────┐
│ │
│ ┌─ times-element : n xs ─┐ │
│ │ ↑ │ │
│ │ └─┐ │ │
│ │ ┌─ lambda : x ─┐│ │ │
│ │ │ ↑ ││ │ │
│ │ │ ┌──┘ ││ │ │
│ │ │ (* x n) ││ │ │
│ │ │ └───┼┘ │ │
│ │ └────────┘ │ │
│ └─────────────┘ │
│ │
└───────────────────┘
図 : ラムダ式内の変数
ポイントは、ラムダ式が関数 times-element 内で定義されているところです。変数 N は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。ラムダ式はその範囲内に定義されているため、変数 N にアクセスすることができるのです。つまり、関数内で定義されたラムダ式は、そのとき有効なレキシカル変数にアクセスすることができるのです。
もうひとつ例題をあげましょう。指定した文字 code が先頭にある文字列を、リストから削除する関数を作ってみましょう。
簡単な実行例を示します。
(remove-string #\a '("abc" "def" "agh" "ijk")) => ("def" "ijk")
リストに格納された文字列の中で、a から始まる文字列を削除します。この処理は、remove-if とラムダ式を使うと簡単に定義できます。
リスト : 先頭文字が code の文字列を削除 (defun remove-string (code xs) (remove-if (lambda (x) (char= code (elt x 0))) xs))
関数 char= は文字型データどうしを比較して、等しいのであれば T を返し、そうでなければ NIL を返します。ラムダ式内で remove-string の引数 CODE にアクセス [*3] できるので、このような定義が可能になるのです。この処理を再帰定義で書くと、次のようになります。
リスト : 先頭文字が code の文字列を削除 (再帰版)
(defun remove-string (code xs)
(cond
((null xs) nil)
((char= code (elt (car xs) 0))
(remove-string code (cdr xs)))
(t (cons (car xs)
(remove-string code (cdr xs)))))
かなり複雑になりますね。ラムダ式と高階関数をうまく組み合わせると、複雑な処理でも簡単にプログラムを記述することができます。
Common Lisp では、関数の中で別の関数を定義することができます。これを「局所関数 (local function)」といいます。局所関数の中では、外側の関数のレキシカル変数にアクセスすることができます。たとえば、関数 foo の中で関数 bar を定義すると、bar の中から foo のレキシカル変数にアクセスすることが可能になります。Pascal をご存知の方にはお馴染みの機能だと思います。
Common Lisp で局所関数を定義するには特殊形式 flet と labels を使います。
(flet ((func1 (args ...) body1) (func2 (args ...) body2) .....) flet-body)
(labels ((func1 (args ...) body1) (func2 (args ...) body2) .....) labels-body)
flet は最初に局所関数を定義して、flet の本体 flet-body を評価します。局所関数は複数定義することができますが、呼び出すことができるのは flet-body の中だけであることに注意してください。labels も同じですが、定義された関数名の有効範囲が少し異なります。
flet の場合、body1 と body2 から関数名 func1 と func2 を参照することはできません。つまり、flet で定義された局所関数は再帰定義や相互再帰ができないのです。labels の場合、body1 と body2 から関数名 func1 と func2 を参照することは可能です。labels では再帰定義や相互再帰を使っても大丈夫ということです。
簡単な実行例を示しましょう。
* (defun foo (a) (flet ((bar () (print a))) (bar))) FOO * (foo 100) 100 100
プログラムに意味はありませんが、関数 foo の引数 A に注目してください。A の有効範囲は foo の中ですが、この中で flet により関数 bar が定義されていますね。この場合、関数 bar はレキシカル変数 A にアクセスできるのです。したがって、(foo 100) を評価するとレキシカル変数 A の値 100 が表示されます。
拙作のページ「末尾再帰」では、階乗を求める関数 fact やフィボナッチ数を求める関数 fibo を末尾再帰に変換するときオプションパラメータを使いました。オプションパラメータを使わずに labels で定義することもできます。プログラムと実行例を示します。
リスト : labels の使用例
;;; 階乗
(defun fact (n)
(labels
((facti (n a)
(if (zerop n)
a
(facti (1- n) (* a n)))))
(facti n 1)))
;;; フィボナッチ数
(defun fibo (n)
(labels
((fiboi (n a b)
(if (zerop n)
a
(fiboi (1- n) b (+ a b)))))
(fiboi n 0 1)))
* (dotimes (x 10) (print (fact x))) 1 1 2 6 24 120 720 5040 40320 362880 NIL * (fact 20) 2432902008176640000 * (dotimes (x 10) (print (fibo x))) 0 1 1 2 3 5 8 13 21 34 NIL * (fibo 40) 102334155
もう一つ簡単な例題として、リストの中から data を見つける find-tree を作りましょう。labels を使わないと、次のようになるでしょう。
リスト : データの探索
(defun find-tree (data tree)
(cond
((atom tree) (eql data tree))
(t (or (find-tree data (car tree))
(find-tree data (cdr tree))))))
* (find-tree 'f '(a b c d e f)) T * (find-tree 'z '(a b c d e f)) NIL * (find-tree 'f '((a . b) (c . d) (e . f))) T * (find-tree 'z '((a . b) (c . d) (e . f))) NIL * (find-tree 'd '(a (b (c (d) e) f) g)) T * (find-tree 'z '(a (b (c (d) e) f) g)) NIL
簡単すぎるので例題には適さないかもしれませんが、ご了承くださいませ。これを labels を使って書き直すと、次のようになります。
リスト : データの探索 (labels版)
(defun find-tree (data tree)
(labels
((find-tree-sub (tree)
(cond ((atom tree) (eql data tree))
(t (or (find-tree-sub (car tree))
(find-tree-sub (cdr tree)))))))
(find-tree-sub tree)))
find-tree-sub から find-tree の引数 data にアクセスすることができます。また、find-tree と find-tree-sub には同じ引数 tree が使われていますね。この場合、find-tree-sub は自分の引数 tree にアクセスします。find-tree の引数 tree は、find-tree-sub から見えなくなることに注意してください。ただし、find-tree-sub の引数 tree を別名にすれば、find-tree の引数 tree にアクセスできるようになります。
それでは「クロージャ (closure)」の話に入りましょう。特殊形式 function (#') のことを思い出してください。function はシンボルに格納されている関数を取り出す働きをします。そして function が返す値が「クロージャ」なのです。クロージャは関数だけではなく、そのときに有効なレキシカル変数とその値も取り出して保存します。
実をいうと、ラムダ式からほかのレキシカル変数にアクセスできるのは、このクロージャが働いているからなのです。次の図を見てください。
(defun foo (a) ───────
(let ((b 20)) ───── ↑
↑ │a
・・１・・ │b │
│ │ (foo 10) を評価した場合
(mapcar (lambda (c) ─── │ │ => #<CLOSURE ... >
↑c │ │ Ｓ式 (lambda (c) ... )
・・２・・ ↓ ↓ │ 環境 ((B . 20) (A . 10))
) b)) ───── │
│
・・３・・ ↓
) ───────
図 : function の評価とクロージャ
上図の場合、mapcar に渡すラムダ式でクロージャが生成されます。このとき有効なレキシカル変数は、関数 foo の引数 A と let で定義された変数 B です。これらの変数と値がクロージャに保持されます。ここではクロージャの構造を単純化して、変数と値は連想リストに格納されていると考えてください。この連想リストを「環境 (environment)」と呼びます。クロージャを評価するときは、取り出した関数をこの「環境」で評価するのです。ここがクロージャを理解するポイントです。
ラムダ式が評価される場合、まず引数の値がセットされますね。たとえば、C に 30 がセットされたとしましょう。すると、クロージャに保持されている環境に (C . 30) が追加されます。
環境 : ((C . 30) (B . 20) (A . 10))
ラムダ式の本体はこの環境で評価されるため、ラムダ式の引数 C 以外のレキシカル変数、つまり foo の引数や let で定義されたレキシカル変数にアクセスできるのです。
次は、クロージャ独特の使い方を見ていきましょう。クロージャは function の返り値です。つまり Lisp で扱うことができるデータのひとつです。ということは、クロージャを変数に代入することもできるはずです。次の例を見てください。
リスト : この関数は何をする？ (defun foo (x) (lambda (y) (* x y)))
関数 foo はクロージャを返します。このクロージャを変数にセットしておいて、funcall や apply などの高階関数を使って呼び出すことができます。次の例を見てください。
* (setq t2 (foo 2))
#<CLOSURE (LAMBDA (Y) :IN FOO) {1001BDCABB}>
* (funcall t2 2)
4
* (funcall t2 4)
8
* (setq t10 (foo 10))
#<CLOSURE (LAMBDA (Y) :IN FOO) {1001BF689B}>
* (funcall t10 1)
10
* (funcall t10 2)
20
この例からもわかるように、変数 t2 に格納されたクロージャを評価すると、引数を 2 倍した値を返します。変数 t10 のクロージャは、引数を 10 倍しています。つまり、関数 foo は引数を定数倍する関数を生成していたのです。
(foo 2) => #<CLOSURE ... >
Ｓ式 (lambda (y) (* x y))
環境 ((X . 2))
(foo 10) => #<CLOSURE ... >
Ｓ式 (lambda (y) (* x y))
環境 ((X . 10))
図 : 関数 foo の評価
(foo 2) を評価すると、そのクロージャには評価する S 式と環境がセットされます。このとき、定義されているレキシカル変数は foo の引数 X だけです。したがって、環境は ((X . 2)) となります。このクロージャを評価するときは、この環境で行われます。したがって、(funcall t2 4) を評価すると、Y = 4, X = 2 なり、ラムダ式の評価結果は 8 となるのです。
(foo 10) の場合も同様です。これは X の値が 10 になるだけです。環境の保存はクロージャを生成するときに行われます。引数 X は同じだからといって、環境も共通で使われるわけではありません。(foo 2) と (foo 10) で生成したクロージャの環境は異なることに注意してください。
それから、局所関数を定義して、その関数を返してもクロージャを生成することができます。次のプログラムを見てください。
リスト : カリー化関数
(defun map-curry (func)
(labels
((map-inner (xs)
(if (null xs)
nil
(cons (funcall func (car xs))
(map-inner (cdr xs))))))
#'map-inner))
上のプログラムは関数 map1 func xs を 1 引数の関数に直したものです。my-curry は関数 func を受け取り、その func を呼び出してリストを操作する関数を返します。これでもマッピングの動作ができるのです。簡単な例を示しましょう。
* (setq foo (map-curry (lambda (x) (* x x))))
#<CLOSURE (LABELS MAP-INNER :IN MAP-CURRY) {1001C156CB}>
* (funcall foo '(1 2 3 4 5))
(1 4 9 16 25)
* (funcall (map-curry (lambda (x) (* x x))) '(1 2 3 4 5))
(1 4 9 16 25)
最初の例は my-curry で生成した関数を変数 foo にセットし、それから foo を funcall で関数呼び出しします。次の例は、my-curry の返り値を直接 funcall に渡して関数呼び出ししています。funcall やカッコが多くなりますが、2 引数の map1 と同じように呼び出すことができます。これでもリストの要素を 2 乗することができます。
2 番目の例は、最初の引数を受け取って新しい関数を生成して返し、その関数に次の引数を適用して値を求めるという動作になります。このように、関数の引数が一つでも「関数を返す関数」を使うことで、複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。
関数型言語には、カリー化関数をサポートしているプログラミング言語、たとえば Haskell や ML (SML/NJ, Ocaml) などがあります。これらのプログラミング言語では、高階関数はカリー化関数として定義されています。また、関数を合成して新しい関数を作ることも簡単にできます。
クロージャの応用例として「ジェネレータ (generator)」というプログラムを作りましょう。ジェネレータは呼び出されるたびに新しい値を生成します。たとえば、関数 random は評価するたびに乱数を返しますね。random は乱数列を発生する「ジェネレータ」と考えることができます。
簡単な例題として、フィボナッチ数 ( 0, 1, 1, 2, 3, 5, 8, ..... ) を発生するジェネレータを作ってみます。関数名は make-fibo としましょう。ジェネレータはスペシャル変数を使って実現することができますが、クロージャを使った方がスマートです。まず、ジェネレータを作る関数を定義します。
リスト : ジェネレータの生成 (1)
(defun make-fibo ()
(let ((a 0) (b 1))
(lambda ()
(prog1 a (psetq a b b (+ a b))))))
関数 make-fibo はクロージャを返します。そして、このクロージャがジェネレータの役割を果たします。
それでは、実際に実行してみましょう。
* (setq f1 (make-fibo))
#<CLOSURE (LAMBDA () :IN MAKE-FIBO) {1001C9219B}>
* (funcall f1)
0
* (funcall f1)
1
* (funcall f1)
1
* (funcall f1)
2
* (funcall f1)
3
* (funcall f1)
5
* (setq f2 (make-fibo))
#<CLOSURE (LAMBDA () :IN MAKE-FIBO) {1001D3175B}>
* (funcall f2)
0
* (funcall f2)
1
make-fibo で作成したクロージャを変数 f1 にセットし、funcall で評価します。0, 1, 1, 2, 3, 5 とフィボナッチ数列を生成していますね。新しいクロージャを変数 f2 にセットし、このクロージャを評価すれば、新しいフィボナッチ数列が生成されます。
クロージャで保存される環境は、let で定義された変数 A と B です。これらの変数は let が評価されたときに初期化される、つまり、クロージャを生成するときに初期化されることに注意してください。
環境はクロージャによって異なります。f1 のクロージャが評価されると、そのクロージャの環境が更新されるのであって、ほかのクロージャに影響を与えることはありません。したがって、あるジェネレータが発生するフィボナッチ数列が、ほかのジェネレータに影響を与えることはないのです。あとは必要な数だけジェネレータを make-fibo で作り、生成したクロージャを変数に格納しておけばいいわけです。
次はフィボナッチ数列を最初に戻す、つまり、ジェネレータをリセットすることを考えましょう。この場合、クロージャ内の変数を書き換えるしか方法はありません。そこで、make-fibo に引数を与えて、value ならばフィボナッチ数列を発生させる、reset ならばリセットするようにしましょう。数列を発生させる処理とリセットする処理をラムダ式で作成し、それを make-fibo の定義するレキシカル変数に格納しておけば、その処理を呼び出すことができます。プログラムは次のようになります。
リスト : ジェネレータの生成 (2)
(defun make-fibo ()
(let* ((a 0) (b 1)
(reset-func (lambda () (setq a 0 b 1)))
(value-func (lambda () (prog1 a (psetq a b b (+ a b))))))
(lambda (type)
(case
type
(reset (funcall reset-func))
(value (funcall value-func))))))
変数 RESET-FUNC にジェネレータをリセットする処理を、VALUE-FUNC にフィボナッチ数列を発生する処理をセットします。レキシカル変数の定義には let* を使っていることに注意してください。これでラムダ式内から変数 A, B にアクセスすることができます。
ジェネレータ本体の処理は、引数が RESET ならば RESET-FUNC を、VALUE ならば VALUE-FUNC を呼び出すだけです。このラムダ式は let* 内で定義されているので、RESET-FUCN と VALUE-FUNC にアクセスすることができます。
それでは実行してみましょう。
* (setq f1 (make-fibo))
#<CLOSURE (LAMBDA (TYPE) :IN MAKE-FIBO) {1001C0562B}>
* (funcall f1 'value)
0
* (funcall f1 'value)
1
* (funcall f1 'value)
1
* (funcall f1 'value)
2
* (funcall f1 'value)
3
* (funcall f1 'reset)
1
* (funcall f1 'value)
0
* (funcall f1 'value)
1
* (funcall f1 'value)
1
正常に動作していますね。リセットの動作はジェネレータを初期化するだけです。リセットの動作でフィボナッチ数列の最初の値を出力してもいいでしょう。簡単に改造できるので試してみてください。
クロージャの話は少し難しかったかもしれません。とくに、ジェネレータのような使い方は、Ｃ言語などの手続き型言語を使いこなしているユーザーでも驚くことなのです。私が参考文献 1 『LISP 原書第 3 版 (1) (2)』でジェネレータのプログラムを見たときは、「Lisp はこんなこともできるのか！」とたいへん驚いたものです。
関数の中で局所関数を定義する、または関数の中でラムダ式を使うとき、クロージャを意識して使うとプログラムが簡単になる場合があります。特に、高階関数と組み合わせて使うとき、クロージャはとても大きな効果を発揮します。最近では、いろいろな言語でラムダ式 (無名関数) やクロージャが取り入れられていますが、Lisp の方が元祖なのです。クロージャは少々歯応えがある機能ですが、これもプログラミングの面白いところだと思います。じっくりとを味わってみてください。
関数 remove-string はクロージャが絡むので、ちょっと難しかったかもしれません。Common Lisp らしくキーワード :key を使うと、もっと簡単にプログラムできます。
リスト : キーワード :key を使う場合 (defun remove-string (code xs) (remove code xs :key (lambda (x) (char x 0))))
文字列の先頭文字を取り出す関数をラムダ式で定義し、それを :key に設定します。あとは、remove がこのラムダ式を呼び出して、先頭文字と CODE を比較します。このプログラムだと、ラムダ式から CODE にアクセスする必要はありません。
次に示す関数を定義してください。
関数 flatmap は次の動作と同じになります。
* (mapcar (lambda (x) (list x x)) '(1 2 3 4 5)) ((1 1) (2 2) (3 3) (4 4) (5 5)) * (apply #'append '((1 1) (2 2) (3 3) (4 4) (5 5))) (1 1 2 2 3 3 4 4 5 5)
mapcar で生成したリストの要素を append で連結するだけです。
リスト : マッピングしたあと平坦化する (defun flatmap (func xs) (apply #'append (mapcar func xs)))
* (flatmap (lambda (x) (list x x)) '(1 2 3 4 5)) (1 1 2 2 3 3 4 4 5 5) * (flatmap (lambda (x) (make-list x :initial-element x)) '(1 2 3 4 5)) (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5)
リスト : pred が真の要素を取り出す
(defun take-while (pred xs)
(if (or (null xs) (not (funcall pred (car xs))))
nil
(cons (car xs) (take-while pred (cdr xs)))))
take-while は XS が空リストまたは述語 PRED が偽を返すとき空リストを返します。そうでなければ、take-while を再帰呼び出しして、その返り値にリストの要素を追加します。
* (take-while (lambda (x) (< x 5)) '(1 2 3 4 5 6 7 8 9)) (1 2 3 4) * (take-while #'plusp '(1 2 3 4 5 6 7 8 9)) (1 2 3 4 5 6 7 8 9) * (take-while #'minusp '(1 2 3 4 5 6 7 8 9)) NIL
リスト : pred が真の要素を取り除く
(defun drop-while (pred xs)
(if (or (null xs) (not (funcall pred (car xs))))
xs
(drop-while pred (cdr xs))))
drop-while は簡単です。リスト XS が空リストまたは述語 PRED が偽を返すとき、リスト XS を返します。そうでなければ、drop-while を再帰呼び出しするだけです。
* (drop-while (lambda (x) (< x 5)) '(1 2 3 4 5 6 7 8 9)) (5 6 7 8 9) * (drop-while #'plusp '(1 2 3 4 5 6 7 8 9)) NIL * (drop-while #'minusp '(1 2 3 4 5 6 7 8 9)) (1 2 3 4 5 6 7 8 9)
リスト : リストの分割
(defun partition-if (pred xs)
(if (null xs)
(values nil nil)
(multiple-value-bind
(ys zs)
(partition-if pred (cdr xs))
(if (funcall pred (car xs))
(values (cons (car xs) ys) zs)
(values ys (cons (car xs) zs))))))
引数 XS が空リストになったら NIL を 2 つ values で返します。ここに XS の要素を格納します。partition-if を再帰呼び出しして、返り値を multiple-value-bind で受け取ります。リストは変数 YS と ZS にセットされます。そして、PRED に (car xs) を適用して、真ならば YS に偽ならば ZS に (car xs) を追加します。あとは values で 2 つのリストを返します。
* (partition-if #'evenp '(1 2 3 4 5 6 7 8 9)) (2 4 6 8) (1 3 5 7 9) * (partition-if #'oddp '(1 2 3 4 5 6 7 8 9)) (1 3 5 7 9) (2 4 6 8) * (partition-if (lambda (x) (< x 5)) '(1 2 3 4 5 6 7 8 9)) (1 2 3 4) (5 6 7 8 9)
リスト : クイックソート
(defun quick-sort (xs pred)
(if (null xs)
nil
(multiple-value-bind
(ys zs)
(partition-if (lambda (x) (funcall pred x (car xs))) (cdr xs))
(append (quick-sort ys pred)
(list (car xs))
(quick-sort zs pred)))))
partition-if に渡す述語はラムダ式です。枢軸はリスト XS の先頭要素ですが、ラムダ式の中から引数 XS を参照できるので、(car xs) で枢軸を求めることができます。
* (quick-sort '(5 6 4 7 3 8 2 9 1 0) #'<) (0 1 2 3 4 5 6 7 8 9) * (quick-sort '(9 8 7 6 5 4 3 2 1 0) #'<) (0 1 2 3 4 5 6 7 8 9) * (quick-sort '(0 1 2 3 4 5 6 7 8 9) #'<) (0 1 2 3 4 5 6 7 8 9)
リスト : 連続した同じ記号を部分リストにまとめる
(defun pack (xs)
(if (null xs)
nil
(cons (take-while (lambda (x) (eql (car xs) x)) xs)
(pack (drop-while (lambda (x) (eql (car xs) x)) xs)))))
* (pack '(a a a b c c c c d d e e e e e)) ((A A A) (B) (C C C C) (D D) (E E E E E))
関数 pack は take-while と drop-while を使うと簡単です。(car xs) と等しい要素を take-while で取り出します。pack を再帰呼び出しするとき、(car xs) と等しい要素を drop-while で取り除きます。
データ内で同じ値が並んでいる場合はその値と個数で符号化する方法のことを、「ランレングス圧縮」または「ランレングス符号化」といいます。
リスト : ランレングス符号化
(defun encode (xs)
(mapcar (lambda (ys) (cons (car ys) (length ys)))
(pack xs)))
関数 encode は pack を使うと簡単です。pack の返り値を mapcar で (code . n) に変換するだけです。
* (encode '(a a a b c c c c d d e e e e e)) ((A . 3) (B . 1) (C . 4) (D . 2) (E . 5))
リスト : ランレングス復号 (defun decode (xs) (flatmap (lambda (ys) (make-list (cdr ys) :initial-element (car ys))) xs))
ランレングスの復号は関数 flatmap と make-list を使うと簡単です。make-list で (code . n) をリストに変換し、flatmap でそれを平坦化するだけです。
* (decode '((A . 3) (B . 1) (C . 4) (D . 2) (E . 5))) (A A A B C C C C D D E E E E E)