Functional Programming

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

前回は高階関数について説明しました。今回は「クロージャ (closure)」を取り上げます。簡単に説明すると、クロージャは評価する関数と参照可能な局所変数を結びつけたものです。クロージャは関数と同じく評価することができますが、クロージャを生成するときに参照可能な局所変数を保持しているところが異なります。参照可能な局所変数の集合を「環境 (environment)」と呼ぶことがあります。

Scheme の場合、関数の実体はラムダ式であり、ラムダ式を評価するとその値はクロージャになります。そして、クロージャを変数に代入するだけで関数を定義することができます。一般に、define で大域的な関数を定義する場合、その時点で定義されている局所変数はないので、クロージャを意識することはありません。

関数の中で局所的な関数を定義する、または関数の中でラムダ式を使うとき、クロージャを意識して使うとプログラムが簡単になる場合があります。とくに、高階関数と組み合わせて使うとき、クロージャはとても大きな効果を発揮します。また、クロージャを使うと関数を生成する関数を簡単に作ることができます。

クロージャは初心者の方にとってちょっと難しい概念かもしれません。クロージャを正しく理解するポイントのひとつに「局所変数の有効範囲」があります。まず最初に、局所変数のアクセスについて、詳しく説明することにしましょう。

●局所変数の有効範囲

次のように、変数 x を表示する関数 foo を定義します。

gosh[r7rs.user]> (define (foo) (display x))
foo
gosh[r7rs.user]> (difine x 10)
x
gosh[r7rs.user]> (foo)
10#<undef>

関数 foo には変数 x の定義はありません。したがって、foo を実行した場合は x を大域変数として扱うので 10 と表示されます。それでは foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には局所変数 x が定義されています。この場合 foo はどちらの値を表示するのでしょうか。

gosh[r7rs.user]> (define (foo1) (let ((x 100)) (foo)))
foo1
gosh[r7rs.user]> (foo1)
10#<undef>

大域変数の値を表示しました。つまり、foo1 で定義した変数 x は foo からアクセスすることはできないのです。簡単なことのようですが、実はとても大事なことなのです。これを図に示すと、次のようになります。

変数の有効範囲を表すのに「スコープ (scope)」という用語 ^[*1] を使います。そして、このようなスコープ規則を「レキシカルスコープ (lexical scope)」といいます。レキシカルとは文脈上という意味があり、変数が定義されている位置によって、その変数にアクセスできるかどうかが決まります。

Shemem や Common Lisp では、関数の仮引数や let などで定義した局所変数は、レキシカルスコープで扱われます。次の例を見てください。

たとえば、(foo2 10) を評価したとしましょう。仮引数 a には 10 がセットされますね。変数 a の値は関数 foo2 の全体で有効です。つまり、foo2 の中で変数 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 だけであり、変数 b と c は大域変数として扱われるのです。

つまり、局所変数はそれを定義した S 式の範囲内でのみ有効なのです。関数の仮引数であれば、それを定義した define の S 式が範囲内であり、let, let* の場合も同じです。定義されていない変数は、すべて大域変数として扱われます。このように、S 式という文脈から局所変数のアクセスを決定できるので、レキシカルスコープ ^[*2] と呼ばれます。

●ダイナミックスコープ

ところが、伝統的な Lisp はレキシカルスコープではありません。たとえば最初の例で、foo1 で定義した変数 x は、呼び出された関数 foo からもアクセスすることができます。これを「ダイナミックスコープ (dynamic scope)」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在し、foo1 から呼ばれた関数ならば、どこからでもアクセスすることができるのです。これを図に示すと次のようになります。

defun は Scheme の define に、print は write に相当する Lisp の関数です。ダイナミックスコープの場合、局所変数はひとつの連想リストで管理されていると考えてください。この場合、キーが局所変数で、データがその値に対応します。局所変数にアクセスするときは、この連想リストから該当する変数を探します。見つからない場合は、大域変数として扱われることになります。

関数呼び出しや let などで局所変数が定義されたとき、変数とその値が連想リストの先頭へ追加されます。そして、関数や let の評価が終了したときに、連想リストから変数が削除されます。関数が呼び出されるたびに、新しい変数が連想リストに追加されますが、呼び出した側で定義した局所変数もこの連想リストの中に残っていることに注意してください。

たとえば、(1) のように、関数 foo を呼び出した場合は、関数の引数がなくて局所変数の定義もないので、連想リストは空です。ところが、(2) のように関数 foo1 を呼び出した場合は、局所変数 x が定義されているので、連想リストに (x . 100) がセットされます。この状態で関数 foo を呼び出すと、連想リストには foo1 で定義した変数 (x . 100) が残っているので、foo では x の値が 100 となるのです。

参照可能な局所変数の集合を「環境 (environment)」といいますが、この局所変数を定義した連想リストを環境と考えるとわかりやすいでしょう。レキシカルスコープの場合は、関数呼び出しが行われるたびに、新しい連想リストが用意され、そこに仮引数や let などで定義された局所変数がセットされます。

ところが、ダイナミックスコープの場合は、ひとつの連想リストで局所変数を管理するので、変数のアクセスは関数を評価する順番に左右されます。したがって、関数の中で定義されていない変数があっても、それが大域変数として扱われるとは限らないのです。

なお、連想リストは説明のために用いたもので、今の実用的な Lisp / Scheme 処理系は、連想リストよりも効率的な方法で局所変数を管理していると思います。ただし、簡単な Lisp 処理系を自作する場合、局所変数の管理に連想リストを使う方法は有効です。興味のある方は拙作のページ Scheme で作る micro Scheme をお読みください。

●ラムダ式と局所変数

今度はラムダ式の場合を考えてみます。次の例を見てください。

リスト : リストの要素を n 倍する

(define (times-element n ls)
  (map (lambda (x) (* x n)) ls))

ラムダ式は関数呼び出しと同じ働きをします。ラムダ式の仮引数は x だけですから、ラムダ式内の変数 n は大域変数をアクセスするように思われるかもしれません。ここで、ラムダ式が定義されている位置に注目してください。ラムダ式は、関数を定義している S 式の中で定義されています。この場合、変数 n は関数 times-element の仮引数 n をアクセスするのです。これを図に示すと、次のようになります。

関数 times-element の中にラムダ式が包み込まれていると考えてください。このように関数内で定義されているラムダ式は、その時点で定義されている局所変数にアクセスすることができるのです。次の図を見てください。

1 の位置では、関数 foo の仮引数 a と let で定義された変数 b が、局所変数として扱われます。次に、ラムダ式内である 2 の位置では、変数 a と b に加えて、ラムダ式の仮引数である c が局所変数として扱われます。a, b, c 以外の変数は大域変数として扱われます。

ラムダ式だけではなく、define で内部関数を定義する場合も同じです。define で内部関数を定義するとき、その時点で有効な外側の関数の局所変数は、内部関数からアクセスすることができます。Scheme の場合、関数の実体はラムダ式であり、関数定義はラムダ式の値を変数に束縛することと同じなので、内部関数のスコープがラムダ式と同じになるのは当然のことなのです。

また、let とラムダ式は同じスコープ規則を持ちますが、実をいうと Scheme の場合、let はラムダ式を使って実現することができます。次の例を見てください。

(let ((x 10) (y 20) (z 30)) (foo x y z))
=> ((lambda (x y z) (foo x y z)) 10 20 30)

let による局所変数の定義は、ラムダ式の呼び出しで仮引数に値を代入することと同じです。このように、ラムダ式は Scheme の基本であり、その背景には「λ計算 (lambda calculus)」という理論があります。

●高階関数とラムダ式

もうひとつ簡単な例題をあげましょう。指定した文字 code が先頭にある文字列を、リストから削除する関数を作ってみましょう。これは、次に示すような処理を行います。

gosh[r7rs.user]> (remove-string #\a '("abc" "def" "agh" "ijk"))
("def" "ijk")

リストに格納された文字列の中で、a から始まる文字列を削除します。まず、この処理を再帰定義で作ってみましょう。処理手順は次のようになります。

引数の文字と文字列の先頭文字が異なっていれば、それをリストに格納して返せばいいわけです。これをプログラムすると、次のようになります。

リスト : 指定した先頭文字の文字列を削除

(define (remove-string c ls)
  (cond
   ((null? ls) '())
   ((char=? c (string-ref (car ls) 0))
    (remove-string c (cdr ls))
   (else
    (cons (car ls) (remove-string c (cdr ls))))))

この処理は前回作成した remove-if とラムダ式を使うと簡単に定義できます。

リスト : 指定した先頭文字の文字列を削除

(define (remove-string c ls)
  (remove-if (lambda (x) (char=? c (string-ref x 0))) ls))

ラムダ式内で remove-string の仮引数 c をアクセスできるので、このようなプログラムが可能になるのです。ラムダ式と高階関数をうまく組み合わせると、複雑な処理でも簡単にプログラムすることができます。

●ラムダ式とクロージャ

それでは、クロージャの話に入ります。クロージャは関数だけではなく、それを評価する「環境」も取り出して保持しています。次の例を見てください。

この例では評価する関数はラムダ式ですね。そして、それを評価する環境は、関数 foo の仮引数 a と let で定義された変数 b です。これが環境 (上図では連想リストで表現) としてクロージャに格納されます。クロージャはこの環境で関数を評価するのです。上図では評価する関数本体を S 式 ^[*3] で表しています。

ここがクロージャを理解するポイントです。ラムダ式が評価される場合、まず仮引数の値がセットされますね。たとえば、c に 30 がセットされたとしましょう。すると、クロージャに保持されている環境に (c . 30) が追加されます。

環境 : ((c . 30) (b . 20) (a . 10))

ラムダ式の本体はこの環境で評価されるため、ラムダ式の仮引数 c 以外の局所変数、つまり foo の仮引数や let で定義された局所変数にアクセスできるのです。これはラムダ式だけではなく、define で内部関数を定義する場合も同じです。どちらの場合も、関数の内部でラムダ式が評価されてクロージャが生成されるので、その時点で有効な局所変数にアクセスすることができるのです。

●関数を生成する関数

今度は、クロージャ独特の使い方を見ていきましょう。クロージャはラムダ式の評価値でしたね。つまり Scheme で扱うことができるデータのひとつです。ということは、クロージャを返す関数を作成することができるはずです。次の例を見てください。

リスト : この関数は何をする？

(define (foo x) (lambda (y) (* x y)))

関数 foo はクロージャを返します。このクロージャを変数にセットしておいて、あとから呼び出すことができます。次の例を見てください。

gosh[r7rs.user]> (define t2 (foo 2))
t2
gosh[r7rs.user]> (t2 4)
8
gosh[r7rs.user]> (t2 5)
10

gosh[r7rs.user]> (define t10 (foo 10))
t10
gosh[r7rs.user]> (t10 1)
10
gosh[r7rs.user]> (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) を評価すると、そのクロージャには評価する関数本体と環境がセットされます。このとき、定義されている局所変数は foo の引数 x だけです。したがって、環境は ((x . 2)) となります。このクロージャを評価するときは、この環境で行われます。したがって、(t2 4) を評価すると y = 4, x = 2 なり、関数の評価結果は 8 となるのです。

(foo 10) の場合も同様ですね。これは x の値が 10 になるだけです。環境の保存はクロージャを生成するときに行われます。仮引数 x は同じだからといって、環境も共通で使われるわけではありません。(foo 2) と (foo 10) で生成したクロージャの環境は異なることに注意してください。

●カリー化

それから、局所的な関数を定義して、その関数を返してもクロージャを生成することができます。次のプログラムを見てください。

リスト : カリー化関数

(define (my-map func)
  (define (map1 ls)
    (if (null? ls)
        '()
        (cons (func (car ls)) (map1 (cdr ls)))))
  map1)

上のプログラムは関数 my-map を 1 引数の関数に直したものです。my-map は関数 func を受け取り、その func を呼び出してリストを操作する関数を返します。これでもマッピングの動作ができるのです。簡単な例を示しましょう。

gosh[r7rs.user]> (import (gauche base))
gosh[r7rs.user]> (define foo (my-map (lambda (x) (* x x))))
foo
gosh[r7rs.user]> (foo '(1 2 3 4 5))
(1 4 9 16 25)
gosh[r7rs.user]> ((my-map (lambda (x) (* x x))) '(1 2 3 4 5))
(1 4 9 16 25)

最初の例は my-map で生成した関数を変数 foo にセットし、それから foo を関数呼び出しします。次の例は、my-map の返り値を直接関数呼び出ししています。カッコが多くなりますが、 2 引数の my-map と同じように呼び出すことができます。これでもリストの要素を 2 乗することができます。

2 番目の例は、最初の引数を受け取って新しい関数を生成して返し、その関数に次の引数を適用して値を求めるという動作になります。このように、関数の引数が一つでも、「関数を返す関数」を使うことで、複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。

関数型言語には、カリー化関数をサポートしているプログラミング言語、たとえば Haskell や ML (SML/NJ, Ocaml) などがあります。これらのプログラミング言語では、高階関数はカリー化関数として定義されています。また、関数を合成して新しい関数を作ることも簡単にできます。

Scheme の場合、カリー化関数はサポートされていませんが、「部分適用」という方法が用意されていて、ライブラリ srfi-26 や Gauche の組み込み関数 pa$ で利用することができます。

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

gosh[r7rs.user]> (import (gauche base))
gosh[r7rs.user]> (define foo (pa$ map (lambda (x) (* x x))))
foo
gosh[r7rs.user]> (foo '(1 2 3 4 5))
(1 4 9 16 25)

部分適用に興味のある方は Gauche のマニュアルをお読みください。

●ジェネレータ

もうひとつクロージャの応用例として、「ジェネレータ (generator)」というプログラムを紹介しましょう。ジェネレータは、呼び出されるたびに新しい値を生成していきます。たとえば、線形合同法の関数 irand は評価するたびに乱数を返しますね。つまり、irand は乱数列を発生する「ジェネレータ」と考えることができます。

簡単な例題として、奇数 (1, 3, 5, ...) を発生するジェネレータを作ってみます。関数名は gen-odd-number としましょう。

gosh[r7rs.user]> (gen-odd-number)
1
gosh[r7rs.user]> (gen-odd-number)
3
gosh[r7rs.user]> (gen-odd-number)
5

gen-odd-number は評価されるたびに、新しい奇数値を返していきます。いちばん簡単な実現方法は、返した値を大域変数に記憶しておくことです。gen-odd-number は次のようにプログラムできます。

リスト : 奇数を発生するジェネレータ

(define *prev-number* -1)

(define (gen-odd-number)
  (set! *prev-number* (+ *prev-number* 2))
  *prev-number*)

大域変数 *prev-number* は、gen-odd-number が返した値を記憶します。新しい値は、この *prev-number* に 2 を足せばいいのです。ただし、*prev-number* は gen-odd-number を評価する前に -1 で初期化しておかなくてはいけません。

このように、大域変数を使うと簡単にジェネレータを作ることができますが、問題点もあります。それは、同じジェネレータを複数使う場合です。たとえば、ある関数 foo でジェネレータを使っているとします。foo は関数 foo1 を呼び出していて、この foo1 でもジェネレータを使います。次の図を見てください。

関数 foo で発生させた数列は 1, 3, 5 でした。ここで関数 foo1 を呼び出します。関数 foo1 でもジェネレータを使うのですが、それは 1, 3, 5, 7, ... という数列が必要です。この場合、foo1 で gen-odd-number を呼び出してはいけません。もし gen-odd-number を呼び出すと、1, 3, 5 ではなく 7, 9, 11 となってしまいます。

したがって、foo1 で使うジェネレータを別に用意しなくてはいけません。そこで、新しい大域変数 *prev-number1* を作り、それをアクセスするジェネレータ gen-odd-number1 を用意します。つまり、ジェネレータの数だけ大域変数と関数を作らなければいけません。ジェネレータの個数が少ない場合は、この方法でも何とか対応できますが、数が増えると大域変数や関数を定義するだけでも大変な作業になります。

ところがクロージャを使うと、もっとスマートにジェネレータを実現できます。まず、ジェネレータを作る関数を定義します。

リスト : ジェネレータを作る関数

(define (make-odd-gen)
  (let ((prev-number -1))
    (lambda ()
      (set! prev-number (+ prev-number 2))
      prev-number)))

関数 make-odd-gen はクロージャを返します。そして、このクロージャがジェネレータの役割を果たすのです。それでは、実際に実行してみましょう。

gosh[r7rs.user]> (define gen-odd-num1 (make-odd-gen))
gen-odd-num1
gosh[r7rs.user]> (gen-odd-num1)
1
gosh[r7rs.user]> (gen-odd-num1)
3
gosh[r7rs.user]> (gen-odd-num1)
5

gosh[r7rs.user]> (define gen-odd-num2 (make-odd-gen))
gen-odd-num2
gosh[r7rs.user]> (gen-odd-num2)
1
gosh[r7rs.user]> (gen-odd-num2)
3

gosh[r7rs.user]> (gen-odd-num1)
7
gosh[r7rs.user]> (gen-odd-num1)
9

make-odd-gen で作成したクロージャを変数 gen-odd-num1 にセットして評価します。評価するたびに 1, 3, 5 と奇数列を生成していますね。次に新しいクロージャを変数 gen-odd-num2 にセットします。このクロージャを評価すると、新しい奇数列を生成します。再び gen-odd-num1 にセットしたクロージャを評価しても、発生する奇数列は乱されていません。make-odd-gen で生成したクロージャは、確かにジェネレータとして機能しています。

このプログラムのポイントは、let で定義された局所変数 prev-number です。次の図を見てください。

クロージャで保存される環境は、let で定義された変数 prev-number です。この値は let が評価されたときに -1 で初期化されています。したがってクロージャに保存される環境は ((prev-number . -1)) となります。次に、gen-odd-num1 にセットしたクロージャを評価します。ラムダ式はクロージャに保存された環境で評価されるので、(+ prev-number 2) の値は 1 になり、set! によりクロージャに保持されている prev-number の値は 1 に更新されるのです。

なお、代入を許さない純粋な関数型言語の場合、クロージャの環境を更新することはできません。Lisp / Scheme は代入により変数の値を書き換えることができるので、クロージャを使ってジェネレータを実現することができます。

環境はクロージャによって異なります。gen-odd-num1 のクロージャが評価されると、そのクロージャの環境が更新されるのであって、ほかのクロージャに影響を与えることはありません。したがって、ジェネレータが発生する奇数列が、ほかのジェネレータに影響を与えることはないのです。あとは必要な数だけジェネレータを make-odd-gen で作り、そのクロージャを変数に格納しておけばいいわけです。

●乱数ジェネレータ

最後に、線形合同法で乱数を生成するプログラムをジェネレータで作ってみましょう。数当てゲーム [1] で作成した線形合同法のプログラムは、整数の乱数を生成する関数 irand と実数の乱数を生成する関数 random の 2 つがありました。この 2 つの関数をひとつのクロージャで実現するため、引数を受け取って処理を切り替えることにしましょう。シンボル irand ならば整数の乱数を返し、シンボル random ならば実数の乱数を返すことにします。

プログラムは次のようになります。

リスト : 乱数の生成

(define (make-random seed)
  (define (irand)
    (set! seed (modulo (+ (* 69069 seed) 1) #x100000000))
    seed)
  (define (random) (* (/ 1.0 #x100000000) (irand)))
  (lambda (x)
    (cond
     ((eq? x 'irand) (irand))
     ((eq? x 'random) (random))
     (else #f))))

関数 make-random は乱数ジェネレータを生成します。引数 seed が乱数の種 (シード) になります。次に、内部関数 irand と random を定義します。それから、ラムダ式でクロージャを生成して返します。引数 x が irand ならば、内部関数 irand を呼び出して整数の乱数を返します。random ならば内部関数 random を呼び出して、実数の乱数を返します。

それでは実行してみましょう。

gosh[r7rs.user]> (define prg (make-random 1))
prg
gosh[r7rs.user]> (prg 'irand)
69070
gosh[r7rs.user]> (prg 'irand)
475628535
gosh[r7rs.user]> (prg 'irand)
3277404108
gosh[r7rs.user]> (prg 'irand)
772999773
gosh[r7rs.user]> (prg 'irand)
3877832058
gosh[r7rs.user]> (prg 'random)
0.889840406132862
gosh[r7rs.user]> (prg 'random)
0.3870111908763647
gosh[r7rs.user]> (prg 'random)
0.4759426398668438
gosh[r7rs.user]> (prg 'random)
0.8821929632686079
gosh[r7rs.user]> (prg 'random)
0.1857799997087568

このように、クロージャに irand を指定すると整数の乱数を、random を指定すると実数の乱数を生成することができます。

●まとめ

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

1. 局所変数はそれを定義した S 式の範囲内でのみ有効 (レキシカルスコープ)。
2. 伝統的な Lisp では関数の評価順序により局所変数の有効範囲が変わる (ダイナミックスコープ)。
3. ラムダ式 (内部関数) はその時点で定義されている局所変数にアクセスできる。
4. クロージャは評価する関数とその環境を保存する。
5. 複数の引数を受け取る関数において、引数をひとつずつ処理していく方法を「カリー化」という。
6. Scheme はカリー化をサポートしていないが、かわりに部分適用という方法がある。
7. ジェネレータは列を発生する。
8. ジェネレータはクロージャを使って実現できる。

クロージャの話は少し難しかったかもしれません。昔の話ですが、筆者が Lisp の勉強でジェネレータのプログラムを初めて見たとき、「Lisp はこんなこともできるのか！」とたいへん驚いたものです。今では、Perl, Python, Ruby などクロージャをサポートしているプログラミング言語はずいぶん多くなりました。クロージャは少々歯応えがある機能ですが、これもプログラミングの面白いところだと思っています。初心者の方もぜひ挑戦してみてください。

●問題

次に示す関数を定義してください。

1. マッピングした結果を平坦化する関数 flatmap func xs
2. 述語 pred を満たす要素が続いている間、リスト xs の先頭から順番に要素を取り出す関数 take-while pred xs
3. 述語 pred を満たす要素が続いている間、リスト xs の先頭から順番に要素を取り除く関数 drop-while pred xs
4. リスト xs の中で連続した等しい要素を部分リストにまとめる関数 pack xs
5. リストの中で連続している同じ記号を (code . num) に変換する関数 encode xs
6. encode xs の逆変換を行う関数 decode xs

●解答１

関数 flatmap は次の動作と同じになります。

gosh[r7rs.user[> (map (lambda (x) (list x x)) '(1 2 3 4 5))
((1 1) (2 2) (3 3) (4 4) (5 5))

gosh[r7rs.user[> (apply append (map (lambda (x) (list x x)) '(1 2 3 4 5)))
(1 1 2 2 3 3 4 4 5 5)

map で生成したリストの要素を append で連結するだけです。

リスト : マッピングしたあと平坦化する

(define (flatmap func xs) (apply append (map func xs)))

gosh[r7rs.user[> (flatmap (lambda (x) (list x x)) '(1 2 3 4 5))
(1 1 2 2 3 3 4 4 5 5)

gosh[r7rs.user[> (flatmap (lambda (x) (make-list x x)) '(1 2 3 4 5))
(1 2 2 3 3 3 4 4 4 4 5 5 5 5 5)

make-list x n は x を n 個格納したリストを生成する関数です。簡単な使用例を示しましょう。

gosh[r7rs.user[> (make-list 10 'a)
(a a a a a a a a a a)

●解答２

リスト : pred が真の要素を取り出す

(define (take-while pred xs)
  (if (or (null? xs) (not (pred (car xs))))
      '()
      (cons (car xs) (take-while pred (cdr xs)))))

take-while は xs が空リストまたは述語 pred が偽を返すとき空リストを返します。そうでなければ、take-while を再帰呼び出しして、その返り値にリストの要素を追加します。

gosh[r7rs.user[> (take-while (lambda (x) (< x 5)) '(1 2 3 4 5 6 7 8 9))
(1 2 3 4)

gosh[r7rs.user[> (take-while positive? '(1 2 3 4 5 6 7 8 9))
(1 2 3 4 5 6 7 8 9)

gosh[r7rs.user[> (take-while negative? '(1 2 3 4 5 6 7 8 9))
()

●解答３

リスト : pred が真の要素を取り除く

(define (drop-while pred xs)
  (if (or (null? xs) (not (pred (car xs))))
      xs
      (drop-while pred (cdr xs))))

drop-while は簡単です。リスト xs が空リストまたは述語 pred が偽を返すとき、リスト xs を返します。そうでなければ、drop-while を再帰呼び出しするだけです。

gosh[r7rs.user[> (drop-while (lambda (x) (< x 5)) '(1 2 3 4 5 6 7 8 9))
(5 6 7 8 9)

gosh[r7rs.user[> (drop-while positive? '(1 2 3 4 5 6 7 8 9))
()

gosh[r7rs.user[> (drop-while negative? '(1 2 3 4 5 6 7 8 9))
(1 2 3 4 5 6 7 8 9)

●解答４

リスト : 連続した同じ記号を部分リストにまとめる

(define (pack xs)
  (if (null? xs)
      '()
      (cons (take-while (lambda (x) (eqv? (car xs) x)) xs)
            (pack (drop-while (lambda (x) (eqv? (car xs) x)) xs)))))

gosh[r7rs.user[> (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 で取り除きます。

●解答５

データ内で同じ値が並んでいる場合はその値と個数で符号化する方法のことを、「ランレングス圧縮」または「ランレングス符号化」といいます。

リスト : ランレングス符号化

(define (encode xs)
  (map (lambda (ys) (cons (car ys) (length ys))) (pack xs)))

関数 encode は pack を使うと簡単です。pack の返り値を map で (code . n) に変換するだけです。

gosh[r7rs.user[> (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))

●解答６

リスト : ランレングス復号

(define (decode xs)
  (flatmap (lambda (ys) (make-list (cdr ys) (car ys))) xs))

ランレングスの復号は関数 flatmap と make-list を使うと簡単です。make-list で (code . n) をリストに変換し、flatmap でそれを平坦化するだけです。

gosh[r7rs.user[> (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)