Functional Programming

Scheme プログラミング中級編 [4]

これまで説明したリスト操作関数は、引数のリストを直接修正せずに新しいリストを生成して返しています。たとえば、append で (a b c) と (d e f) を連結する場合、最初の引数 (a b c) はそのままで、2 つのリストを連結した新しいリスト (a b c d e f) を作っています。つまり、(a b c) はコピーされているわけです。

このように、リストを操作する関数の多くが新しいリストを生成して返しますが、プログラムによっては引数のリストを直接修正（破壊的修正）した方が便利な場合もあります。今回は Scheme に用意されているリストを破壊的に修正する関数を説明します。

●リスト構造の修正

Scheme の基礎知識 [1] で説明したように、リストは複数のコンスセルを接続して構成されています。コンスセルにはデータを格納する CAR 部とコンスセルをつなぐ CDR 部という場所があります。Scheme にはコンスセルを直接書き換える関数 set-car! と set-cdr! が用意されています。

• set-car! cell obj
• set-cdr! cell obj

set-car! はコンスセル cell の CAR 部を obj に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CAR 部を書き換えます。set-car! の返り値は未定義です。簡単な例を示しましょう。

gosh[r7rs.user]> (define z (list 'a 'b 'c))
z
gosh[r7rs.user]> z
(a b c)
gosh[r7rs.user]> (set-car! z 'd)
#<undef>
gosh[r7rs.user]> z
(d b c)

変数 z にリスト (a b c) をセットします。set-car! はコンスセルの CAR 部、この場合は (a b c) の先頭セルの CAR 部を a から d に書き換えます。リストの CAR 部を直接書き換えるので、変数 z の値も (d b c) になることに注意してください。次の図を見てください。

上図に示すように、変数 z はリスト (a b c) を格納しています。set-car! は変数 z が格納しているコンスセルの CAR 部を直接 d に書き換えるので、変数 z の値も (d b c) になるのです。このように、set-car! には副作用があるので使用には十分な注意が必要です。

set-cdr! はコンスセル cell の CDR 部を obj に書き換えます。cell にリストが与えられた場合は、先頭のコンスセルの CDR 部を書き換えます。set-cdr! の返り値は未定義です。簡単な例を示しましょう。

gosh[r7rs.user]> (define z (list 'a 'b 'c))
z
gosh[r7rs.user]> z
(a b c)
gosh[r7rs.user]> (set-cdr! z 'd)
#<undef>
gosh[r7rs.user]> z
(a . d)

set-cdr! はコンスセルの CDR 部、この場合は (a b c) の先頭セルの CDR 部を d に書き換えます。次の図を見てください

上図に示すように、CDR 部にはコンスセルがつながっていますが、それをシンボル d に書き換えるのですから後ろのコンスセルは切断されて、変数 z の値は (a . d) というドット対になります。set-cdr! にも副作用があることに注意してください。

●リストの連結

リストを連結する関数に append がありますが、引数のリストは破壊されません。append の動作を図 (再掲) に示します。

                  図 : append の動作

このように append は第 1 引数のリストをコピーしてから連結します。これに対し、引数のリストをコピーせずに、最後尾のセルの CDR 部を書き換えることで、リストを連結する関数を考えることができます。Common Lisp では nconc と呼ばれている関数ですが、Scheme の仕様 (R5RS, R7RS-small) にはありません。ライブラリ SRFI-1 には append! という関数が用意されています。

• append! list1 list2 ...

関数 append! は引数のリストをつなぎあわせたリストを返します。最後を除く引数の内容が破壊されます。次の図を見てください。

上図に示すように、append! はリストの最終セルの CDR 部を直接書き換えることで、引数のリストを連結しています。

簡単な例を示しましょう。

gosh[r7rs.user]> (import (srfi 1))
gosh[r7rs.user]> (define x (list 'a 'b 'c))
x
gosh[r7rs.user]> (define y (list 'd 'e 'f))
y
gosh[r7rs.user]> (append! x y)
(a b c d e f)
gosh[r7rs.user]> x
(a b c d e f)
gosh[r7rs.user]> y
(d e f)

Gauche の R7RS モードで SRFI-1 を使う場合は (import (srfi 1)) を入力してください。これでライブラリ SRFI-1 をロードすることができます。変数 x と y に格納されているリストを append! で連結します。このとき、変数 x の値は書き換えられることに注意してください。

●リストの反転

関数 reverse はリストの要素を逆順にした新しいリストを生成して返します。ここで、リストを破壊的に修正する関数 reverse! を考えてみましょう。SRFI-1 には reverse! が用意されていますが、私たちでもプログラムすることができます。次の図を見てください。

変数 ls に格納されたリストを逆順にします。このとき、変数 r に逆順のリストを保持します。考え方は簡単で、リストの先頭から要素を順番に取り出して、変数 r のリストに追加していくところは reverse と同じです。この操作をセルをつなぎかえることで行っているのが reverse! です。つまり、セルごと要素を移動しているのです。

これをプログラムすると次のようになります。

リスト : リストの反転 (破壊的操作)

(define (reverse! ls)
  (let loop ((ls ls) (r '()))
    (if (null? ls)
        r
        (let ((x (cdr ls)))
          (set-cdr! ls r)
          (loop x ls)))))

reverse! は引数 ls のリストを破壊的な操作で要素を逆順にします。変数 r に逆順のリストを保持します。ls が空リストの場合は r を返します。そうでなければ、ls の先頭のセルを r に追加します。

まず、2 番目のセルを変数 x にセットします。それから、先頭セルの CDR 部を r に書き換えます。これで、r の先頭にセルを移動することができます。あとは、loop を再帰呼び出しするとき、第 1 引数に x を、第 2 引数に ls を渡します。ls の先頭のセルが逆順のリストの先頭になっていることに注意してください。

それでは簡単な例を示しましょう。

gosh[r7rs.user]> (define a (list 1 2 3 4))
a
gosh[r7rs.user]> a
(1 2 3 4)
gosh[r7rs.user]> (define b (reverse! a))
b
gosh[r7rs.user]> b
(4 3 2 1)
gosh[r7rs.user]> a
(1)

reverse! の返り値を代入した変数 b の値は逆順のリストになっています。ところが、変数 a の値は逆順のリストになっていません。reverse! は変数 a のリストを破壊的に修正しますが、変数 a の値が逆順のリストになるわけではありません。これは SRFI-1 の関数 reverse! も同じ動作になります。ご注意くださいませ。

●リストによるキューの実装

それでは簡単な例題として、リストを使って「キュー (queue)」という基本的なデータ構造を実装してみましょう。なお、Gauche にはキューを操作するライブラリ util.queue が用意されていますが、Scheme のお勉強ということで、実際にプログラムを作ってみましょう。

キューは「待ち行列」といわれるデータ構造です。たとえば、チケットを買う場合窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。

このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。

キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。

たとえば、データの追加に append を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると実行時間がかかるようになります。そこで、append の代わりに append! を使うことを考えてみます。この場合、リストのコピーは回避できますが、最後尾のセルは先頭から順番にセルをたどっていかないと到達できないので、データが多くなるとやっぱり時間がかかってしまいます。

そこで、最後尾のセルを格納する変数を用意することにします。

上図に示すように、リストを保持する変数 front のほかに、最後尾のセルを格納する変数 rear を用意します。このようなデータ構造を作成する場合、R7RS-small では「レコード型」というデータ構造を使うところですが、まだ説明していないので、今回はクロージャを使ってプログラムを作ることにします。

キューを操作するプログラムは次のようになります。

リスト : リストによるキューの実装

(define (make-queue)
  (let ((front '()) (rear '()))
    ;; キューにデータを追加する
    (define (enqueue! item)
      (let ((new-cell (list item)))
        (if (null? front)
            ;; キューは空
            (set! front new-cell)
            ;; 最後尾のセルを書き換える
            (set-cdr! rear new-cell))
        (set! rear new-cell)))
    ;; キューからデータを取り出す
    (define (dequeue!)
      (if (null? front)
          #f
          (let ((item (car front)))
            (set! front (cdr front))
            ;; キューは空になったか？
            (when (null? front) (set! rear '()))
            item)))
    ;;
    (lambda (x . args)
      (cond
       ((eq? x 'enqueue!)
        (enqueue! (car args)))
       ((eq? x 'dequeue!)
        (dequeue!))
       ((eq? x 'empty?)
        (null? front))
       (else #f)))))

関数 make-queue は空のキューを生成し、その操作を行うクロージャを返します。let で局所変数 front と rear を定義して空リストに初期化します。define と同様に、let の先頭部分でも内部関数を定義することができます。

内部関数 enqueue! はキューにデータを入れる処理を行います。最初に、item をリストに格納して new-cell にセットします。変数 front が空リストの場合、キューは空なので、front に new-cell をセットします。キューにデータがある場合は、最後尾のセル rear の CDR 部を set-cdr! で書き換えて new-cell を連結します。最後に new-cell を rear にセットして最後尾のセルを更新します。

キューからデータを取り出す内部関数が dequeue! です。front が空リストの場合、キューにデータはないので #f を返します。キューにデータがある場合は、先頭の要素を取り出して変数 item にセットします。それから、front の先頭のセルを削除します。この操作でキューが空になった場合は、変数 rear に空リストをセットします。これでキューを空にすることができます。

最後にラムダ式でクロージャを返します。enqueue! と dequeue! で引数の個数が違うので、ラムダ式は可変個の引数を受け取るように定義します。

●可変個引数

Scheme の場合、ラムダ式の仮引数は次に示す 3 通りのパターンがあります。

1. (lambda (a b c) ... )
2. (lambda (a b c . args) ... )
3. (lambda args ... )

1 は今までの関数呼び出しと同じ形式で、3 個の仮引数 a, b, c があります。この場合、実引数も 3 個必要になります。2 はドットリストで仮引数を表していて、仮引数 a, b, c は 1 と同じですが、引数 args には残りの引数がリストに格納されて渡されます。つまり、3 個以上の引数を受け取ることができます。3 のように変数 args だけの場合、与えられた引数すべてがリストに格納されて args に渡されます。引数がない場合、args は空リストになります。つまり、0 個以上の引数を受け取る関数になります。

簡単な例を示しましょう。

gosh[r7rs.user]> ((lambda (a b c . args) (list a b c args)) 1 2 3)
(1 2 3 ())
gosh[r7rs.user]> ((lambda (a b c . args) (list a b c args)) 1 2 3 4 5 6)
(1 2 3 (4 5 6))
gosh[r7rs.user]> ((lambda args (list args)))
(())
gosh[r7rs.user]> ((lambda args (list args)) 1 2 3)
((1 2 3))

このように、可変個の引数を受け取る関数を定義することができます。

ラムダ式 (lambda (x . args) ...) は、引数 x に呼び出す内部関数の種類を指定し、残りの引数は args に渡されます。x がシンボル enqueue! の場合は、内部関数 enqueue! を呼び出します。このとき、args の先頭の要素をキューに追加するデータとして渡します。dequeue! の場合は内部関数 dequeue! を呼び出します。empty? はキューが空の場合は #t を返す述語とします。この処理は (null? front) だけなので、ラムダ式の中で処理します。

●case-lambda

引数の個数によって関数の動作を変更したい場合、ライブラリ (scheme case-lambda) に定義されているシンタックス形式 case-lambda を使うと簡単です。

(case-lambda
  (formals1 expr1 ...)

    ...

  (formalsN exprN ...))


図 : case-lambda の構文

formals はラムダ式の仮引数リストと同じ形式です。case-lambda は実引数と formals を順番に照合し、マッチングする節を選択して本体 expr を評価します。マッチングする節が無い場合はエラーになります。簡単な例を示しましょう。

gosh[r7rs.user]> (define foo (case-lambda ((a) (list 'one a)) ((a b) (list 'two a b))))
foo
gosh[r7rs.user]> (foo 1)
(one 1)
gosh[r7rs.user]> (foo 1 2)
(two 1 2)
gosh[r7rs.user]> (foo 1 2 3)
*** ERROR: wrong number of arguments to case lambda: (1 2 3)
Stack Trace:
・・・省略・・・

(foo 1) は最初の節 ((a) ...) とマッチングするので、返り値は (one 1) となります。(foo 1 2) は 2 番目の節 ((a b) ...) とマッチングするので、返り値は (two 1 2) となります。(foo 1 2 3) はマッチングする節が無いのでエラーとなります。なお、formals に可変個引数を指定すると、どんな引数にもマッチングします。

gosh[r7rs.user]> (define bar (case-lambda (rest (list rest))))
bar
gosh[r7rs.user]> (bar)
(())
gosh[r7rs.user]> (bar 1)
((1))
gosh[r7rs.user]> (bar 1 2 3 4)
((1 2 3 4))

可変個引数を使うと、どんな引数にもマッチングするので、それ以降の節は選択されることがありません。ご注意くださいませ。

R7RS-small の関数 member は第 3 引数に等値を判定する述語を渡すことができますが、case-lambda を使うと簡単に定義することができます。次のリストを見てください。

リスト : リストの探索

(define my-member
  (case-lambda
    ((x xs) (my-member x xs equal?))
    ((x xs pred) (cond
                  ((null? xs) #f)
                  ((pred x (car xs)) xs)
                  (else
                   (my-member x (cdr xs) pred))))))

引数が 2 つの場合、第 3 引数に述語 equal? を渡して my-member を呼び出します。引数が 3 つの場合が my-member の本体です。第 3 引数の述語 pred で x とリストの要素 (car xs) を比較し、等しければリスト xs を返します。そうでなければ、my-member を再帰呼び出しして、次の要素と比較します。

簡単な実行例を示します。

gosh[r7rs.user]> (my-member '(5 6) '((1 2) (3 4) (5 6)))
((5 6))
gosh[r7rs.user]> (my-member '(5 6) '((1 2) (3 4) (5 6)) eqv?)
#f

リスト (5 6) を探しますが、引数が 2 つの場合は述語 equal? が適用されるので (5 6) を見つけることができます。第 3 引数に述語 eqv? を指定すると、eqv? はリスト同士の比較は #f を返すので、(5 6) を見つけることができずに #f を返します。

●実行例

これでプログラムは完成です。それでは実行してみましょう。

gosh[r7rs.user]> (define q (make-queue))
q
gosh[r7rs.user]> (for-each (lambda (x) (q 'enqueue! x)) '(1 2 3 4 5))
#<undef>
gosh[r7rs.user]> (do () ((q 'empty?)) (display (q 'dequeue!)) (newline))
1
2
3
4
5
#t
gosh[r7rs.user]> (q 'empty)
#t

正常に動作していますね。

●循環リスト

リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」といいます。次の図を見てください。

                  図 : 循環リスト

リスト (a b c) は空リストで終端されています。このリストで、最後尾のセルの CDR 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。それでは、実際に循環リストを作ってみましょう。

gosh[r7rs.user]> (define z (list 'a 'b 'c))
z
gosh[r7rs.user]> (set-cdr! (cddr z) z)
#<undef>
gosh[r7rs.user]> z
#0=(a b c . #0#)
gosh[r7rs.user]> (car (cdddr z))
a

(cddr z) で最後尾のセルを取り出して、set-cdr! で CDR 部を先頭のセルに書き換えます。Gauche の場合、循環リストは #0=(a b c . #0#) と表示されます。循環リストに終わりはないので、最後の例のように cdr を 3 回適用すると先頭の要素 a が表示されます。

Common Lisp や Scheme (srfi-38) では、#n= により Scheme (Lisp) データにラベルを付けることができます。n には整数値を指定し、#n# でそのデータを参照することができます。#0=(a b c . #0#) の場合、#0= で先頭のセルにラベルがつけられ、最後尾のセルの CDR 部で先頭のセルを #0# で参照しています。これで循環リストを表すことができます。

また、#n= と #n# はプログラムで使うことができます。たとえば、(define z '#0=(a b c . #0#)) とすれば、循環リストを生成して変数 z にセットすることができます。ほかの例も示しましょう。

gosh[r7rs.user]> (define a '("abc" "abc"))
a
gosh[r7rs.user]> (define b '(#0="abc" #0#))
b
gosh[r7rs.user]> (eq? (car a) (cadr a))
#f
gosh[r7rs.user]> (eq? (car b) (cadr b))
#t

Scheme (Lisp) の場合、リスト ("abc" "abc") の 2 つの文字列 "abc" は別々のデータとして生成されるのが普通です。したがって、2 つの文字列を eq? で比較すると #f になります。ところが (#0="abc" #0#) とすると、最初の文字列にラベルが付けられて次の要素でその文字列を参照しているので、リストは同一の文字列データを格納することになります。よって、リストの第 1 要素と第 2 要素を eq? で比較すると #t になるのです。

それから、循環リストを display で表示しようとすると、(a b c a b c a b c ... のように人が手動で中断しない限り止まらなくなります。ご注意くださいませ。

なお、ライブラリ srfi-1 には循環リストを生成する関数 circular-list が用意されています。実際に循環リストを作る場合は、この関数を使用するとよいでしょう。

●循環リストのチェック

循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。

リスト : 循環リストのチェック

(define (my-circular-list? ls)
  (if (or (null? ls) (null? (cdr ls)))
      #f
      (let loop ((fast (cddr ls)) (slow (cdr ls)))
        (cond 
         ((null? fast) #f)
         ((eq? fast slow) #t)
         (else
          (loop (cddr fast) (cdr slow)))))))

SRFI-1 には述語 circular-list? が定義されているので、名前は my-circular-list? としました。変数 fast が「うさぎ」で slow が「かめ」を表します。fast は cddr で、slow は cdr で進みます。fast が終端に到達すれば循環リストではありません。#f を返します。うさぎがかめに追いつくと fast と slow の値は同じセルになるので、(eq? fast slow) の評価結果は真になります。この場合は #t を返します。あとは、リストをたどってチェックを続行します。

それでは実際に試してみましょう。

gosh[r7rs.user]> (my-circular-list? '#0=(a b c . #0#))
#t
gosh[r7rs.user]> (my-circular-list? '#0=(a b . #0#))
#t
gosh[r7rs.user]> (my-circular-list? '#0=(a . #0#))
#t
gosh[r7rs.user]> (my-circular-list? '(a b c d))
#f
gosh[r7rs.user]> (my-circular-list? '())
#f

正常に動作していますね。

●循環リストによるキューの実装

簡単な例題として、今度は循環リストを使って「キュー (queue)」を実装してみましょう。循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。

               図 : 循環リストによるキューの構造

循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、rear が参照する最後尾のセルの CDR 部は空リストではありません。CDR 部が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように rear が参照するセルの CDR 部は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように空リストとします。

●プログラムの作成

それではプログラムを作りましょう。次のリストを見てください。

リスト : 循環リストによるキューの実装

(define (make-queue)
  (let ((rear '()))
    ;; キューへデータを追加
    (define (enqueue! item)
      (let ((new-cell (list item)))
        (cond
         ((null? rear)
          ;; キューは空
          (set-cdr! new-cell new-cell))
         (else
          (set-cdr! new-cell (cdr rear))
          (set-cdr! rear new-cell)))
          (set! rear new-cell)))
    ;; キューからデータを取り出す
    (define (dequeue!)
      (if (null? rear)
          #f
          (let ((front (cdr rear)))
            (if (eq? front rear)
                (set! rear '())
                (set-cdr! rear (cdr front)))
            (car front))))
    ;;
    (lambda (x . args)
      (cond
       ((eq? x 'enqueue!)
        (enqueue! (car args)))
       ((eq? x 'dequeue!)
        (dequeue!))
       ((eq? x 'empty?)
        (null? rear))
       (else #f)))))

関数 make-queue は空のキューを生成し、その操作を行うクロージャを返します。let で局所変数 rear を定義して空リストに初期化します。次に、内部関数 enqueue! を定義します。最初に、item をリストに格納して new-cell にセットします。変数 rear が空リストの場合、キューは空なので new-cell の CDR 部を自分自身に書き換えてから、最後で rear にセットします。

キューにデータがある場合は、rear の後ろに new-cell を連結します。まず、new-cell の CDR 部を (cdr rear) に書き換えます。これで new-cell の後ろに先頭のセルが接続されます。それから、rear の CDR 部を new-cell に書き換えます。これで、rear と先頭のセルの間に new-cell を挿入することができます。最後に new-cell を rear にセットします。

次に dequeue! を定義します。rear が空リストの場合、キューにデータはないので #f を返します。キューにデータがある場合は、先頭のセル (cdr rear) を変数 front にセットします。front と rear が eq? で等しい場合、最後のデータを取り出してキューは空になります。この場合、rear に空リストをセットします。そうでなければ、rear の CDR 部を (cdr front) に書き換えて、front のセルを循環リストから外します。最後に front の要素 (car front) を返します。

●実行例

これでプログラムは完成です。それでは実行してみましょう。

gosh[r7rs.user]> (define q (make-queue))
q
gosh[r7rs.user]> (for-each (lambda (x) (q 'enqueue! x)) '(1 2 3 4 5))
#<undef#>
gosh[r7rs.user]> (do () ((q 'empty?)) (display (q 'dequeue!)) (newline))
1
2
3
4
5
#t
gosh[r7rs.user]> (q 'empty)
#t

正常に動作していますね。

●まとめ

今回はここまでです。簡単に復習しておきましょう。

1. set-car! はリストの CAR 部を破壊的に修正する。
2. set-cdr! はリストの CDR 部を破壊的に修正する。
3. append! は引数のリストを破壊的に修正して複数のリストを連結する。
4. reverse! は引数のリストを破壊的に修正してリストの要素を反転する。
5. キュー (queue) は先入れ先出し (FIFO) のデータ構造である。
6. Scheme は可変個の引数を受け取る関数を定義できる。
7. 引数の個数で関数の動作を変更したい場合は case-lambda を使うとよい。
8. 循環リストは要素をリング状に並べたリストである。

次回は「二分木 (binary tree)」というプログラムでよく用いられるデータ構造を紹介します。