Scheme プログラミング中級編 [1]
前回までは、Lisp / Scheme の特徴である「リスト」を基本にして、簡単なプログラムを作ってきました。前回までを「初級編」とするならば、いよいよ今回から「中級編」へとステップアップします。
Scheme には、リストのほかにもおもしろい機能や特徴があります。最近の手続き型言語、とくにスクリプト言語は Lisp / Scheme からいろいろな機能を取り込んでいるので、以前に比べあっと驚くようなことは少なくなりましたが、それでも Scheme から学ぶことはまだまだあると思っています。今回は関数型言語でよく使われる「高階関数」を中心に、Scheme らしい機能を説明します。
●高階関数
Ｃ言語や Pascal が「手続き型言語」と呼ばれるのに対し、Lisp / Scheme は「関数型言語」と呼ばれています。関数型言語は、データに関数を適用していくことでプログラムを実行します。たとえば、数学の関数を考えてください。
f(x, y) = 2x + 3y
関数 f(x, y) は引数 x と y を与えると値を返します。そして、同じ値の引数を与えれば、結果はいつも同じ値になります。関数型言語の基本的な考え方は、このような数学の関数と同じです。
ところが、Lisp / Scheme は完全な関数型言語ではありません。引数以外の変数を定義して、define や set! で値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
それから、関数型言語の場合、関数はほかのデータと同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することができます。関数を引数として受け取る関数を「汎関数 (functional)」とか「高階関数 (higher order function)」と呼びます。
Scheme などの関数型言語にとって、高階関数は特別なものではありません。Lisp / Scheme には便利な高階関数がいろいろと用意されていますし、私たちユーザーが定義することも簡単にできるのです。最初に、マップ関数から説明しましょう。
●マップ関数
Scheme の場合、繰り返し処理といえば「再帰定義」ですね。単純な繰り返しならば、末尾再帰 (名前付き let) を使うことができます。このほかに、Lisp / Scheme には「マップ関数 (mapping function)」という便利な関数が用意されています。
簡単な例題として、リストの要素どうしを足し算して、その結果をリストに格納する関数を作ってみましょう。つまり、次のような処理を行います。
( 1 2 3 4 5)
+ (10 20 30 40 50)
---------------------
(11 22 33 44 55)
図 : 要素どうしの足し算
これを再帰定義でプログラムすると、次のようになるでしょう。
リスト : リストの要素を足し算する
(define (add-element x y)
(if (null? x)
'()
(cons (+ (car x) (car y))
(add-element (cdr x) (cdr y)))))
関数名は add-element としました。ところで、そろそろ「再帰定義」にも慣れてきたと思いますが、add-element の処理内容は理解できたでしょうか。よく分からない方は、次の処理手順を見て考えてください。
実は、この処理はマップ関数 map だけで実現できるのです。まずは、実行例を見てください。
gosh[r7rs.user]> (add-element '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55) gosh[r7rs.user]> (map + '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55)
+ は足し算をする関数でした。関数の処理内容はシンボルに格納されています。つまり、map には + に格納されている関数を渡しているのです。Gauche の場合、+ の値を表示すると次のようになります。
gosh[r7rs.user]> + #<subr (+ :rest args)>
Gauche の場合、プリミティブの関数は #<subr (名前 引数 ...)> と表示されます。このように、関数を引数として渡すことができるのが Lisp / Scheme の特徴のひとつです。map は渡された関数をリストの各要素に適用して、その結果をリストに格納して返します。もし、各要素に対して乗算 * を適用したい場合は、関数 * を map に渡せばいいのです。
gosh[r7rs.user]> (map * '(1 2 3 4 5) '(10 20 30 40 50)) (10 40 90 160 250)
もちろん、私たちが定義した関数を渡すこともできます。もし、リストの要素を 2 乗したい場合は、数を 2 乗する関数 square を定義して、それを map に渡せばいいのです。
gosh[r7rs.user]> (define (square x) (* x x)) square gosh[r7rs.user]> (map square '(1 3 4 5 7)) (1 9 16 25 49)
map を使う場合、渡された関数にとって必要なだけの引数を用意しないと、当然のことですがエラーになります。引数のリストの長さが異なる場合は、短いリストの要素がなくなった時点で処理を終了します。
gosh[r7rs.user]> (map cons '(a b c d) '(1 2 3 4 5)) ((a . 1) (b . 2) (c . 3) (d . 4))
なお、シンタックス形式の関数を map に渡すことはできません。その場合はエラーになります。
●マップ関数の作成
それではここでマップ関数を作ってみましょう。プログラムを簡単にするため、マップ関数に渡すことができる関数は引数をひとつだけ取るものに限定します。プログラムは次のようになります。
リスト : マップ関数
(define (my-map func ls)
(if (null? ls)
'()
(cons (func (car ls)) (my-map func (cdr ls)))))
関数名は my-map としました。引数 func はリストの要素に適用する関数です。func を呼び出す方法は、今までの関数呼び出しとまったく同じで、リストの先頭の要素に func を書くだけです。func に格納された値は関数なので、func を評価するとその「関数」が得られます。リストの先頭の要素が関数なので、Scheme は func に格納されている値を関数として呼び出すのです。もしも、func の値が関数でなければエラーになります。
ちなみに、Common Lisp の場合、変数 func に格納された関数をそのまま呼び出すことはできません。funcall という特別な関数を使って、(funcall func ...) というようにプログラムする必要があります。関数の扱い方は Scheme の方が関数型言語らしくてすっきりしていると思います。
●フィルター
フィルター (filter) はリストの要素に述語 predicate を適用し、predicate が真を返す要素をリストに格納して返す関数です。
ところで、Scheme の仕様書 (R5RS, R7RS-small) は必要最低限の機能しか定義されていないため、多くの Scheme 処理系で機能追加や拡張が行われています。この拡張機能の標準化を目的に SRFI (Scheme Requests For Implementation) という仕様が定められています。Gauche でも多くの SRFI がサポートされています。
その中で、SRFI-1 にはリスト操作を行う関数が多数定義されています。SRFI-1 には filter や remove という関数が定義されていますが、ここでは Scheme の勉強のため、述語が真を返す要素を削除する関数 remove-if を作ってみましょう。名前は Common Lisp から拝借しました。
リスト ; 述語が真となる要素を削除する
(define (remove-if predicate ls)
(cond
((null? ls) '())
((predicate (car ls))
(remove-if predicate (cdr ls)))
(else
(cons (car ls) (remove-if predicate (cdr ls))))))
remove-if も簡単ですね。要素に predicate を適用して結果が真ならば要素をリストに加えません。結果が偽ならば要素をリストに加えるだけです。簡単な実行例を示しましょう。
gosh[r7rs.user]> (remove-if odd? '(1 2 3 4 5)) (2 4) gosh[r7rs.user]> (remove-if even? '(1 2 3 4 5)) (1 3 5)
odd? は引数が奇数のときに #t を返す述語で、even? は偶数のときに #t を返す述語です。remove-if に odd? を渡すとリストから奇数の要素を削除することができ、even? を渡すと偶数の要素を削除することができます。
もちろん、フィルターも簡単に定義することができます。remove-if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。
リスト : 述語が真となる要素を取り出す
(define (filter predicate ls)
(cond
((null? ls) '())
((predicate (car ls))
(cons (car ls) (filter predicate (cdr ls))))
(else
(filter predicate (cdr ls)))))
簡単な実行例を示しましょう。
gosh[r7rs.user]> (filter odd? '(1 2 3 4 5)) (1 3 5) gosh[r7rs.user]> (filter even? '(1 2 3 4 5)) (2 4)
前回作成したコマンドラインパラメータからオプションを取り出す関数 get-option やオプションを取り除く関数 remove-option は、フィルターを使うと簡単にプログラムすることができます。
リスト : オプションの取得と削除 ;;; オプションか？ (define (option? item) (char=? #\- (string-ref item 0))) ;;; オプションを取り出す (define (get-option ls) (filter option? ls)) ;;; オプションを取り除く (define (remove-option ls) (remove-if option? ls))
関数 option? は - で始まる文字列ならば #t を、そうでなければ #f を返します。オプションを取り出す get-option は filter に option? を渡すだけで実現できます。オプションを取り除く remove-option は remove-if に option? を渡すだけです。
●畳み込み
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を次のように適用します。
(1) (a1 a2 a3 ... an-1 an) => (f (f ... (f (f a1 a2) a3) ...) an-1) an) (2) (a1 a2 a3 ... an-1 an) => (f a1 (f a2 (f a3 ... (f an-1 an) ... )))
関数 f を適用する順番で 2 通りの方法があります。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 : reduce => a1 + a2 + a3 + ... + an-1 + an
このように、reduce はリストのすべての要素を関数 f を用いて結合します。この操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は次のような動作になります。
(1) (a1 a2 a3 ... an-1 an) => (f ... (f (f g a1) a2) ...) an-1) an) (2) (a1 a2 a3 ... an-1 an) => (f a1 (f a2 (f a3 ... (f an g) ...)))
SRFI-1 には fold, fold-right, reduce, reduce-right という同等の機能を持つ関数が定義されているので、ここでは (1) の動作を行う関数 foldl と、(2) の動作を行う関数 foldr を作ってみましょう。プログラムは次のようになります。
リスト : 畳み込み
(define (foldl f g ls)
(if (null? ls)
g
(foldl f (f g (car ls)) (cdr ls))))
(define (foldr f g ls)
(if (null? ls)
g
(f (car ls) (foldr f g (cdr ls)))))
第 1 引数 f が適用する関数、第 2 引数 g が初期値、第 3 引数がリストです。最初に、ls が空リストかチェックします。これが再帰呼び出しの停止条件になりますが、foldl, foldr に空リストが与えられた場合にも対応します。この場合は初期値 g を返します。次の else 節で関数 f を適用して foldl, foldr を再帰呼び出しします。
foldl の場合、引数 g とリストの要素が関数 f の引数になり、その返り値が foldl を再帰呼び出しするときの第 2 引数 g になります。つまり、リストの要素が f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。
foldr の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。foldr はリストの最後尾から処理を行うため、foldr を再帰呼び出しした結果を関数 f の第 2 引数に渡します。
たとえば、(foldr f g '(a1 a2 a3)) は次のように展開されます。
(foldr f g (a1 a2 a3))
↓
(f a1 (foldr f g (a2 a3)))
↓
(f a1 (f a2 (foldr f g (a3))))
↓
(f a1 (f a2 (f a3 (foldr f g ()))))
↓
(f a1 (f a2 (f a3 g)))
図 : foldr の動作
これで reduce の (2) の動作を実現することができます。それでは、簡単な実行例を示しましょう。
gosh[r7rs.user]> (foldl + 0 '(1 2 3 4 5)) 15 gosh[r7rs.user]> (foldr + 0 '(1 2 3 4 5)) 15 gosh[r7rs.user]> (foldl cons '() '(a b c d e)) (((((() . a) . b) . c) . d) . e) gosh[r7rs.user]> (foldr cons '() '(a b c d e)) (a b c d e) gosh[r7rs.user]> (foldl list 0 '(1 2 3 4 5)) (((((0 1) 2) 3) 4) 5) gosh[r7rs.user]> (foldr list 6 '(1 2 3 4 5)) (1 (2 (3 (4 (5 6)))))
cons や list を用いてリストの要素を結合してみると、畳み込みの動作や foldl と foldr の違いがよくわかると思います。
●畳み込みの応用例
ところで、foldl, foldr と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。たとえば、length, map, filter などの例を示します。
リスト : 畳み込みの応用例
;;; リストの長さ
(define (my-length ls)
(define (f x y) (+ x 1))
(foldl f 0 ls))
;;; 述語が真となる要素を数える
(define (count-if predicate ls)
(define (f x y)
(if (predicate y) (+ x 1) x))
(foldl f 0 ls))
;;; マップ関数
(define (my-map f ls)
(define (f1 x y) (cons (f x) y))
(foldr f1 '() ls))
;;; フィルター
(define (my-filter f ls)
(define (f1 x y)
(if (f x) (cons x y) y))
(foldr f1 '() ls))
foldl の場合、関数 f の第 2 引数にリストの要素、第 1 引数に今までの計算結果が渡されます。したがって、my-length は初期値を 0 にして第 1 引数の値を +1 することで実現できます。count-if は Common Lisp の関数と同じで、条件を満たしている要素の個数を数えます。関数 f の引数 y を predicate に適用し、真を返す場合は x を +1 します。
foldr の場合、関数 f の第 1 引数にリストの要素、第 2 引数に今までの計算結果が渡されます。したがって、my-map は初期値を空リストにして、第 1 引数の計算結果を第 2 引数のリストに追加するだけです。my-filter の場合も初期値を空リストにして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。
なお、どちらの関数も局所関数から引数 f の関数を呼び出しています。Scheme の場合、局所関数から外側の関数の局所変数にアクセスすることができます。このことについては次回で詳しく説明します。
●apply
次は apply を説明します。
- apply func args-list
apply は最初の引数 func を関数として呼び出します。このとき、第 2 引数のリストの要素が func の引数として渡されます。apply は func の評価結果を返します。簡単な使用例を示しましょう。
gosh[r7rs.user]> (apply + '(1 2 3)) 6 gosh[r7rs.user]> (apply car '((1 2 3))) 1
また apply は次のように、func と args-list の間に引数を与えることができます。
gosh[r7rs.user]> (apply + 4 5 6 '(1 2 3)) 21
apply はリストに格納されている要素を引数として関数に渡す場合に便利です。
●ラムダ式
ところで、高階関数を使うようになると、数を 2 乗する square のような小さな関数を、いちいち定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。
このような場合、Lisp / Scheme では「ラムダ式 (lambda expression)」を使うことができます。ラムダはギリシャ文字の λ のことです。それでは、理屈はともかくラムダ式の使用例を見てください。
gosh[r7rs.user]> (map (lambda (x) (* x x)) '(1 2 3 4 5)) (1 4 9 16 25)
(lambda (x) (* x x)) がラムダ式です。このように、ラムダ式はリストで、かつ、その第 1 要素には lambda というシンボルがセットされています。ラムダ式の構造は、関数を定義する define とよく似ています。
define と関数名の代わりに lambda を書かけば、あとは define と全く同じです。実は、define で定義する関数の実体がこのラムダ式なのです。次の例を見てください。
gosh[r7rs.user]> (lambda (x) (* x x)) #<closure (#f x)> gosh[r7rs.user]> (define square (lambda (x) (* x x))) square gosh[r7rs.user]> (square 10) 100
Scheme の場合、ラムダ式を評価すると関数を表すデータになります。Scheme ではこれを「クロージャ (closure)」といいます。クロージャには重要な働きがあるのですが、ここではクロージャは関数を表すデータ型のひとつと考えてください。クロージャについては次回で詳しく説明します。
そして、このクロージャを define で変数に束縛すれば、関数を定義することができるのです。Scheme プログラマの中には、ラムダ式による関数定義を好む人も多いようです。また、次のようにラムダ式をリストの先頭要素にもってくれば、それを評価することができます。
gosh[r7rs.user]> ((lambda (x) (* x x)) 2) 4
このように、ラムダ式を使えば名前のない関数を定義することができます。ちなみに 参考文献 1 によると、『昔の Lisp プログラムは最初はラムダ式で書かれていた』 とのことです。このドキュメントでは、関数を定義する define から説明しましたが、Lisp の歴史ではラムダ式の方が先輩だったのですね。
高階関数でラムダ式を使うのは便利で、なおかつ、その場で実行される処理内容が確認できるという利点があります。しかし、同じラムダ式があちこちに現れるようでは問題があります。プログラムに変更はつきもので、もし、その処理を変更しようとした場合、該当するラムダ式をすべて修正しなくてはなりません。これは面倒なことですね。この場合は、define で関数を定義した方がよいのです。そうすると、その関数を修正するだけで済みます。
●リストの探索
ところで、リストに同じ要素があるか調べる場合、Scheme では関数 memq, memv, member を使用することが多いと思います。これらの関数は等値関係を述語 eq?, eqv?, equal? でテストしますが、場合によってはある条件を満たす要素を探したいこともあります。
このような場合、リストを探索する関数を高階関数として定義しておくと便利です。実際、R7RS-Small の member には要素を比較する関数を第 3 引数に渡すことができます。ここでは Scheme の勉強のため、リストを探索する関数を実際に作ってみましょう。
最初は関数 find を作ります。find はリストの中から predicate が真を返す最初の要素を返します。find はリストの先頭から順番に探索します。見つからない場合は #f を返します。プログラムは次のようになります。
リスト : リストの探索
(define (find predicate ls)
(cond
((null? ls) #f)
((predicate (car ls)) (car ls))
(else
(find predicate (cdr ls)))))
リスト ls の要素を先頭から順番に調べていきます。ls が空リストの場合は探索失敗なので #f を返します。リストの要素に predicate を適用して真となる場合はその要素を返します。そうでなければ次の要素を調べます。
簡単な使用例を示します。
gosh[r7rs.user]> (find odd? '(1 2 3 4 5 6)) 1 gosh[r7rs.user]> (find (lambda (x) (< 10 x)) '(5 10 15 20 25)) 15 gosh[r7rs.user]> (find negative? '(5 10 15 20 25)) #f
次は find と似ていますが、見つけた要素の位置を返す関数 position を作ります。次のリストを見てください。
リスト : 見つけた要素の位置を返す
(define (position predicate ls)
(let loop ((ls ls) (n 0))
(cond
((null? ls) #f)
((predicate (car ls)) n)
(else
(loop (cdr ls) (+ n 1))))))
position はリストの中から predicate が真となる最初の要素の位置を返します。局所変数 n で要素の位置を求めます。predicate が真となる要素を見つけたら n を返します。次の要素を調べるときは、変数 n の値を +1 することをお忘れなく。
簡単な使用例を示しましょう。
gosh[r7rs.user]> (position even? '(1 2 3 4 5 6)) 1 gosh[r7rs.user]> (position odd? '(1 2 3 4 5 6)) 0 gosh[r7rs.user]> (position negative? '(1 2 3 4 5 6)) #f
最後に、述語が真となる要素を数える関数 count を作ります。foldl を使わなくても末尾再帰でプログラムを作ることができます。次のリストを見てください。
リスト : 述語が真となる要素を数える
(define (count predicate ls)
(let loop ((ls ls) (n 0))
(cond
((null? ls) n)
((predicate (car ls))
(loop (cdr ls) (+ n 1)))
(else
(loop (cdr ls) n)))))
predicate が真となる要素を局所変数 n でカウントします。find, position と違って、リストを最後まで調べることに注意してください。リスト ls が空リストの場合、変数 n の値を返します。loop を再帰呼び出しする場合、predicate が真のときは n を +1 して、そうでなければ n の値はそのままです。
簡単な使用例を示しましょう。
gosh[r7rs.user]> (count odd? '(1 2 3 4 5 6)) 3 gosh[r7rs.user]> (count (lambda (x) (< 10 x)) '(5 10 15 20 25)) 3 gosh[r7rs.user]> (count negative? '(5 10 15 20 25)) 0
ところで、数当てゲーム [2] で「マスターマインド」を作成しましたが、bulls を数える関数 count-bulls を再帰定義で作りましたね。実は、今回説明した map と count を組み合わせると、とても簡単に count-bulls を作ることができるのです。
まず、再帰版のプログラムを再度示しましょう。
リスト : bulls を求める (再帰版)
(define (count-bulls answer data)
(cond
((null? answer) 0)
((= (car answer) (car data))
(+ 1 (count-bulls (cdr answer) (cdr data))))
(else
(count-bulls (cdr answer) (cdr data)))))
count-bulls は同じ位置にある要素を比較して、等しい要素の個数を数えます。この「同じ位置にある要素を比較する」処理は map を使えば簡単に実現できます。
gosh[r7rs.user]> (map = '(1 2 3 4) '(1 4 3 6)) (#t #f #t #f)
map に関数 = を渡せば、2 つのリストの要素を比較して、その結果をリストに格納して返します。あとは count で #t の個数を数えればいいのです。したがって count-bulls は次のようになります。
リスト : bulls を求める(map 版) (define (count-bulls answer data) (count (lambda (x) x) (map = answer data)))
(lambda (x) x) は引数をそのまま返す関数になります。これを「恒等関数 (identity function)」といいます。map の返り値は真偽値のリストなので、count には恒等関数を渡せば #t の個数をカウントすることができます。
●連想リスト
ここでもうひとつ、Lisp / Scheme らしいデータ構造を紹介しましょう。「連想リスト (association list : alist)」はドット対を要素とするリストです。ドット対の CAR 部がキーで、CDR 部がデータに対応します。次の図を見てください。
上図の場合、a, c, e, g がキーで、b, d, f, h がデータとなります。キーやデータはシンボル以外の S 式でもかまいません。そして、連想リストからデータを探索する関数が assq, assv, assoc です。
- assq obj alist
- assv obj alist
- assoc obj alist [compare]
assoc は member と同様に Lisp の伝統的な関数です。assoc は連想リスト alist から obj と等しいキーを探します。見つからない場合は #f を返します。等値関係のテストは member と同様に、assq が eq? を、assv が eqv? を、assoc が equal? を用います。R7RS-small では assoc の第 3 引数に比較関数を渡すことができるようになりました。
簡単な使用例を示しましょう。
gosh[r7rs.user]> (define z '((a . b) (c . d) (e . f) (g . h))) z gosh[r7rs.user]> (assoc 'e z) (e . f) gosh[r7rs.user]> (assoc 'h z) #f
assq, assv, assoc は、見つけたキーのデータを返すのではなく、ドット対を返すことに注意してください。
●まとめ
今回はここまでです。簡単に復習しておきましょう。
- map はリストの要素に関数を適用し、結果をリストにして返す。
- filter は述語が真を返す要素をリストに格納して返す。
- foldl, foldr はリストの畳み込み (縮約) を行う。
- apply は関数を引数として受け取ってそれを実行する。
- ラムダ式は名前のない関数を定義する。
- SRFI-1 にはリストを操作する便利な関数が定義されている。
- 連想リストはキーとデータのドット対を要素とするリストである。
- 連想リストからキーを探索する関数には assq, assv, assoc がある。
次回は「クロージャ」について説明します。
●参考文献
- 黒川利明,『LISP 入門』, 培風館, 1982
●問題
次に示す関数を定義してください。
- s から e までの整数に関数 fn を適用し、その合計値を求める関数 sum-of fn e s
- s から e までの整数に関数 fn を適用し、その結果をリストに格納して返す関数 tabulate fn e s
- リスト xs の要素に関数 fn を適用するが、その結果を累積しない関数 my-for-each fn xs
- 関数 fn にリストを渡すマップ関数 maplist fn xs
- リスト xs を先頭から畳み込むとき、計算途中の累積値をリストに格納して返す scan-left fn a xs
- リスト xs を末尾から畳み込むとき、計算途中の累積値をリストに格納して返す scan-right fn a xs
- キーを格納したリスト ks と値を格納したリスト vs から連想リストを生成する関数 pairlis ks vs alist
●解答１
リスト : 関数 fn を適用した結果の合計値を求める
(define (sum-of fn s e)
(let loop ((s s) (a 0))
(if (> s e)
a
(loop (+ s 1) (+ a (fn s))))))
gosh[r7rs.user]> (sum-of (lambda (x) x) 1 10) 55 gosh[r7rs.user]> (sum-of (lambda (x) (* x x)) 1 10) 385 gosh[r7rs.user]> (sum-of (lambda (x) (* x x x)) 1 10) 3025
●解答２
リスト : 関数 fn を適用した結果をリストに格納して返す
(define (tabulate fn s e)
(if (> s e)
'()
(cons (fn s) (tabulate fn (+ s 1) e))))
gosh[r7rs.user]> (tabulate (lambda (x) x) 1 10) (1 2 3 4 5 6 7 8 9 10) gosh[r7rs.user]> (tabulate (lambda (x) (* x x)) 1 10) (1 4 9 16 25 36 49 64 81 100) gosh[r7rs.user]> (tabulate (lambda (x) (* x x x)) 1 10) (1 8 27 64 125 216 343 512 729 1000)
●解答３
リスト : 関数 fn を適用するだけ (結果は捨てる) (define (my-for-each fn xs) (when (pair? xs) (fn (car xs)) (my-for-each fn (cdr xs))))
gosh[r7rs.user]> (my-for-each display '(1 2 3 4 5 6 7 8)) 12345678#<undef> gosh[r7rs.user]> (my-for-each (lambda (x) (display x) (newline)) '(1 2 3 4 5 6 7 8)) 1 2 3 4 5 6 7 8 #<undef>
Scheme (R5RS, R7RS-small) には同様の働きをする関数 for-each があります。
gosh[r7rs.user]> (for-each display '(1 2 3 4 5 6 7 8)) 12345678#<undef> gosh[r7rs.user]> (for-each (lambda (x) (display x) (newline)) '(1 2 3 4 5 6 7 8)) 1 2 3 4 5 6 7 8 #<undef>
●解答４
リスト : 関数 fn にリストを渡すマップ関数
(define (maplist fn xs)
(if (null? xs)
'()
(cons (fn xs) (maplist fn (cdr xs)))))
maplist は関数 fn にリスト xs をそのまま渡します。そして、再帰呼び出しするとき xs に cdr を適用します。
gosh[r7rs.user]> (maplist (lambda (x) x) '(a b c d e)) ((a b c d e) (b c d e) (c d e) (d e) (e)) gosh[r7rs.user]> (maplist length '(a b c d e)) (5 4 3 2 1)
●解答５
リスト : 累積値リストの生成 (1)
(define (scan-left fn a xs)
(if (null? xs)
(list a)
(cons a (scan-left fn (fn (car xs) a) (cdr xs)))))
gosh[r7rs.user]> (scan-left + 0 '(1 2 3 4 5 6 7 8 9 10)) (0 1 3 6 10 15 21 28 36 45 55) gosh[r7rs.user]> (scan-left cons '() '(a b c d e)) (() (a) (b a) (c b a) (d c b a) (e d c b a)) gosh[r7rs.user]> (scan-left * 1 '(1 2 3 4 5 6 7 8 9 10)) (1 1 2 6 24 120 720 5040 40320 362880 3628800)
scan-left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan-left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan-left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。
●解答６
リスト : 累積値リストの生成 (2)
(define (scan-right fn a xs)
(if (null? xs)
(list a)
(let ((ys (scan-right fn a (cdr xs))))
(cons (fn (car xs) (car ys)) ys))))
gosh[r7rs.user]> (scan-right + 0 '(1 2 3 4 5 6 7 8 9 10)) (55 54 52 49 45 40 34 27 19 10 0) gosh[r7rs.user]> (scan-right cons '() '(a b c d e)) ((a b c d e) (b c d e) (c d e) (d e) (e) ())
scan-right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。リスト xs が空リストの場合は (list a) を返します。そうでなければ、scan-right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値と xs の要素を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。
●解答７
リスト : 連想リストの生成
(define (pairlis ks vs alist)
(if (or (null? ks) (null? vs))
alist
(cons (cons (car ks) (car vs))
(pairlis (cdr ks) (cdr vs) alist))))
gosh[r7rs.user]> (pairlis '(a b c d e) '(1 2 3 4 5) '()) ((a . 1) (b . 2) (c . 3) (d . 4) (e . 5)) gosh[r7rs.user]> (pairlis '(a b c d e) '(1 2 3 4 5) '((x . 10) (y . 20))) ((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (x . 10) (y . 20))
改訂 2020 年 8 月 30 日