一般に、関数の返り値はひとつしかありません。複数の値を返す場合、昔の Lisp ではリストに格納して返すのが普通でした。この場合、返す側は必要なデータをリストに格納し、受け取る側はリストからデータを取り出す処理が必要になります。ところが、Scheme や Common Lisp の「多値 (multiple values)」という機能を使うと、複数の値を簡単にやり取りすることができます。
Scheme で複数の値を受け取るには関数 call-with-value を使います。
call-with-values producer consumer
call-with-values は producer を評価します。producer は引数のない関数で複数の値 (多値) を返します。call-with-value はそれをそのまま cousumer に渡して評価します。その結果が call-with-values の返り値となります。
複数の値を返すには関数 values を使います。
values args ...
values は複数個の引数を多値として返します。簡単な例を示しましょう。
gosh[r7rs.user]> (values 1 2 3) 1 2 3 gosh[r7rs.user]> (call-with-values (lambda () (values 1 2 3)) list) (1 2 3)
(values 1 2 3) は 3 つの値 1, 2, 3 を返します。call-with-values は受け取った多値を list に渡すので、(list 1 2 3) が評価されて (1 2 3) が返り値となります。
もう一つ簡単な例題として、Scheme のライブラリ SRFI-1 に用意されている関数 partition を作ってみましょう。
partition pred ls
partition はリスト ls を述語 pred で二分割し、pred を満たす要素のリストと、pred を満たさない要素のリストの 2 つを多値として返します。プログラムは次のようになります。
リスト : リストの分割 (1)
(define (partition pred ls)
(if (null? ls)
(values '() '())
(call-with-values
(lambda ()
(partition pred (cdr ls)))
(lambda (a b)
(if (pred (car ls))
(values (cons (car ls) a) b)
(values a (cons (car ls) b)))))))
引数 ls が空リストの場合は values で空リストを 2 つ返します。そうでなければ、call-with-values の最初のラムダ式で partition を再帰呼び出しし、2 番目のラムダ式の引数 a, b で多値を受け取ります。(pred (car ls)) が真の場合、(car ls) を a の先頭に追加し、そうでなければ b の先頭に追加します。あとは values で 2 つのリストを返すだけです。
簡単な実行例を示します。
gosh[r7rs.user]> (partition even? '(1 2 3 4 5 6)) (2 4 6) (1 3 5) gosh[r7rs.user]> (partition odd? '(1 2 3 4 5 6)) (1 3 5) (2 4 6)
このように、多値の操作は multiple-value-bind と values を使って行うことができます。このほかにも、便利な関数やマクロがあるので紹介しましょう。多値を変数に取り出す場合、R7RS-small で定義されているマクロ let-values, let*-values を使うと便利です。
(let-values ((variables mv-expr) ...) body ...) (let*-values ((variables mv-expr) ...) body ...)
variables はシンボルのリストで、mv-expr は多値を返す関数です。mv-expr が返す多値を variables のシンボルに束縛し、body 以降の S 式を評価します。多値の個数と変数の個数が合わないとエラーになります。let-values と let*-values は let と let* の関係と同じです。簡単な使用例を示します。
gosh[r7rs.user]> (let-values (((a b) (values 1 2)) ((c d) (values 3 4))) (list a b c d)) (1 2 3 4) gosh[r7rs.user]> (let*-values (((a b) (values 1 2)) ((c d) (values a b))) (list a b c d)) (1 2 1 2)
let-values を使うと、リストを分割する parititon は次のようになります。
リスト : リストの分割 (2)
(define (partition2 pred ls)
(if (null? ls)
(values '() '())
(let-values (((a b) (partition2 pred (cdr ls))))
(if (pred (car ls))
(values (cons (car ls) a) b)
(values a (cons (car ls) b))))))
gosh[r7rs.user]> (partition2 odd? '(1 2 3 4 5 6)) (1 3 5) (2 4 6) gosh[r7rs.user]> (partition2 even? '(1 2 3 4 5 6)) (2 4 6) (1 3 5)
partition2 を再帰呼び出しするとき、let-values で多値を受け取って変数 a, b にセットするだけです。call-with-values よりも使いやすいと思います。
define-values は多値の define バージョンです。
(define-values variables mv-expr)
varibales はシンボルのリストですが、ドットリストは受け付けないので注意してください。mv-expr は多値を返す関数です。簡単な使用例を示しましょう。
gosh[r7rs.user]> (define-values (a b) (values 1 2)) b gosh[r7rs.user]> a 1 gosh[r7rs.user]> b 2
最後に簡単な例題として「クイックソート (quick sort)」を取り上げます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でもクイックソートは高速なアルゴリズムとして有名です。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。
枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3 1 2 4) 5 (7 6 9 8)
3を枢軸に分割 7を枢軸に分割
(1 2) 3 (4) | 5 | (6) 7 (9 8)
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト : クイックソート
(define (quick-sort f ls)
(if (null? ls)
'()
(let ((p (car ls)))
(let-values (((a b) (partition (lambda (x) (f x p)) (cdr ls))))
(append (quick-sort f a)
(cons p (quick-sort f b)))))))
最初に ls が空リストかチェックします。これが再帰呼び出しの停止条件になります。そうでなければ、リストを分割してソートを行います。リストの先頭要素を取り出して変数 p にセットします。これが枢軸となります。
リストの分割は関数 partition で行います。partition は x を基準にリストを 2 つに分割し、それらのリストを多値で返します。要素の大小関係は述語 pred で判定します。これを let-values で受け取り、変数 a, b にセットします。
リスト a が枢軸よりも小さな要素を集めたもので、リスト b が枢軸以上の要素を集めたものです。そして、quick-sort を再帰呼び出しして、リスト a, b をソートします。あとは、その結果を枢軸 p を挟んで結合すればいいわけです。
それでは、簡単な実行例を示しましょう。
gosh[r7rs.user]> (quick-sort < '(5 6 4 7 3 8 2 9 1)) (1 2 3 4 5 6 7 8 9) gosh[r7rs.user]> (quick-sort > '(5 6 4 7 3 8 2 9 1)) (9 8 7 6 5 4 3 2 1)
正常に動作していますね。
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。
たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。
たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
ただし、この改良方法はリストには不向きであることに注意してください。リストはデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。このため、リストのソートはクイックソートよりも「マージソート (merge sort)」の方が適しているといわれています。
多値と同じような動作は「継続渡しスタイル (CPS)」でも実現することができます。CPS についての詳しいは説明は、拙作のページ「継続と継続渡しスタイル」をお読みください。
今までは「継続」に渡す引数をひとつに限定していましたが、これを複数の引数を渡すように拡張します。たとえば、リストを分割する partition を CPS でプログラムすると次のようになります。
リスト : リストの分割 (CPS 版)
(define (partition/cps pred ls cont)
(if (null? ls)
(cont '() '())
(partition/cps
pred
(cdr ls)
(lambda (xs ys)
(if (pred (car ls))
(cont (cons (car ls) xs) ys)
(cont xs (cons (car ls) ys)))))))
partition/cps の引数 cont が継続を表します。cont は 2 つの引数を受け取ります。ls が空リストの場合は cont に 2 つの空リストを渡します。
parition/cps は継続 (ラムダ式) の引数 xs, ys に 2 つのリストを渡します。この中で ls の先頭要素に述語 pred を適用して、真ならば xs の先頭に要素を追加し、そうでなければ ys の先頭に追加します。最後に、2 つのリストを cont に渡して呼び出すだけです。
簡単な実行例を示します。
gosh[r7rs.user]> (partition/cps even? '(1 2 3 4 5 6 7 8) (lambda (a b) (list a b))) ((2 4 6 8) (1 3 5 7))
partition/cps を使ったクイックソートは次のようになります。
リスト : クイックソート (CPS 版)
(define (quick-sort f ls)
(if (null? ls)
'()
(let ((p (car ls)))
(partition/cps
(lambda (x) (f x p))
(cdr ls)
(lambda (a b)
(append (quick-sort f a)
(cons p (quick-sort f b))))))))
partition/cps に渡す継続 (ラムダ式) で 2 つのリストを受け取り、この中で quick-sort を再帰呼び出しします。そして、その結果を枢軸 p を挟んで append で結合すればいいわけです。
簡単な実行例を示します。
gosh[r7rs.user]> (quick-sort < '(5 6 4 7 3 8 2 9 1 10)) (1 2 3 4 5 6 7 8 9 10)
Scheme の多値は R5RS から導入された比較的新しい機能です。多値は Scheme の「継続 (continuation)」を使って実装されています。通常、継続に渡す引数はひとつだけなのですが、call-with-values, let-values, let*-values, define-values のもとで生成された継続に限り、任意の数の引数を渡すことができます。
R7RS-small では values を次のように定義しています。
リスト : values の定義 (R5RS, R7RS-small)
(define (values . things)
(call-with-current-continuation
(lambda (cont) (apply cont things))))
call/cc で取り出した継続 cont に複数の値を渡して呼び出しているだけです。この定義からもわかるように、(values) とすると 0 個の引数を継続に渡すことができます。簡単な例を示します。
gosh[r7rs.user]> (list) () gosh[r7rs.user]> (call-with-values (lambda () (values)) list) ()
ただし、引数をひとつ受け取る継続に 0 または 2 個以上の引数を渡した場合の動作は R7RS-small に規定されていません。処理系依存の動作になります。Gauche の場合、引数が 0 個のときは #<undef> が渡され、2 個以上のときは最初の要素が渡されます。
簡単な例を示しましょう。
gosh[r7rs.user]> (define a #f) a gosh[r7rs.user]> (display (call/cc (lambda (k) (set! a k) 1))) 1#<undef> gosh[r7rs.user]> (a 2) 2#<undef> gosh[r7rs.user]> (a 1 2 3) 1#<undef> gosh[r7rs.user]> (a) #<undef>#<undef>
display の引数を評価するときの継続を取り出して変数 a にセットします。これは引数をひとつ受け取る継続です。(a 2) を評価すると、2 が display に渡されて 2 が表示されます。(a 1 2 3) を評価すると、最初の引数 1 が display に渡されます。(a) を評価すると #<undef> が渡されます。
ただし、処理系によって動作が異なる可能性があります。引数の個数が合わない場合、エラーを送出する処理系があるかもしれません。ご注意くださいませ。