いままでの合計を求めるプログラムは、「1 から連続する数の合計」を求めるものだったけど、例えばテストの点数や、みんなの身長とか、靴のサイズなどの連続していない数や、同じ数が現れるかもしれない場合には向いていませんでした。
今回は、
・連続しない数
・重複するかもしれない数
があったとしても合計できるプログラムについて考えていこう。
リスト
今迄のプログラムは 1 から連続する数の合計を求めるプログラムだったので、引数に最後の数だけ指定すれば良かったわけ。1000 までの合計ならば
(goukei 1000)
と書けばいいね。この goukei 手続きは、1 から連続した数を合計する事を暗黙の前提としていたので、連続しない数だったり、重複するかもしれない数を合計する場合は、この前提が崩れてしまうから使えないわけだね。
さて、どうしよう。
1 つの答は、引数に合計したい数を列挙するという方法。Scheme では値を列挙するときに「リスト」を使います。
(goukei '(60 75 95 55 75))
例えばこんな感じ。引数に指定している
'(60 75 95 55 75)
この部分がリストです。この書き方ならば、数が連続している必要もないし、同じ値の数が複数あったとしても問題にならないよね。
Scheme では単にカッコでくくると手続きの評価を意味するので、リストとして扱いたい場合はアポストロフィー「'」を付けて、これは手続きの実行じゃなくてリストだよってことを Scheme に教えてあげないといけない。アポストロフィーをつけるのを忘れてしまうと...
gosh> (60 75 95 55 75) *** ERROR: invalid application: (60 75 95 55 75) Stack Trace: _______________________________________ 0 (eval expr env) at "/usr/local/share/gauche-0.97/0.9.9/lib/gauche/interactive.scm":269
このようにエラーになってしまう。
これは「60」っていう名前の手続きに「75 95 55 75」という 4 つの引数を渡して、評価するという意味になってしまうからだね。「60」っていう名前の手続きは定義していないので、Scheme は「そんな手続き知らない」とエラーを返すわけ。
POINT : リストを書くときは、アポストロフィーをつけるのを忘れない事!
ところで、Scheme 言語は、Lisp 言語の 1 種類なんだけれども、Lisp 言語の名前の由来は 「LISt Processor」から来ているんだ。つまり Lisp はリストを処理する言語ってこと。で、Scheme 言語は Lisp の仲間で、その 1 種類なので、Scheme もリストを処理する言語です。Scheme 言語において、リストはとても大切なデータ構造なので、リストについて深く理解することは、Scheme でプログラミングする上でとても重要なので覚えてください。
ペアとリスト
いきなりですが、はじめにリストの定義を書きます。
『リストとは、(要素 . リスト) で構成される「ペア」の再帰的構造を言う。』
いきなりこんな事言われても、なんの事かよくわからないよねw
順を追って説明するから心配はいらない。リストについて詳しく説明する前に、
まずリストを構成する要素「ペア」について説明していこう。
ペアというのは 2 つのものを 1 つにまとめたもので、Scheme では
cons (コンスと読みます)という手続きを使って作ります。
gosh>(cons 3 4) (3 . 4)
ペアは通常、かっこでくくって、要素をピリオドで区切って表現します。
では、このペアの要素を取り出してみよう。
最初の要素を取り出すには car (カーと読みます)を使います。
gosh> (car (cons 3 4)) 3
最初の要素以外を取り出すには cdr (クダーと読みます)を使います。
gosh> (cdr (cons 3 4)) 4
ここで『え? 「最後」じゃなくて「最初の要素以外」なんてどうして言うの ???』と思ったそこの君!
君はするどいね。目のつけどころがシャープだね!w
これは後で説明するから、もうちょっと待ってください。
次のように cons をたくさん組み合せて複雑なペアを作る事もできます。
gosh> (cons (cons (cons 1 2) (cons 3 4)) (cons (cons 5 6) (cons 7 8))) (((1 . 2) 3 . 4) (5 . 6) 7 . 8)
car や cdr を使って、それぞれの要素の取り出しの練習をしてみてください。
一旦 pairs に define してから練習をしてみよう。
gosh> (define pairs (cons (cons (cons 1 2) (cons 3 4)) (cons (cons 5 6) (cons 7 8)))) pairs
pairs
とすれば中身が表示できるよ。
gosh> pairs (((1 . 2) 3 . 4) (5 . 6) 7 . 8)
ちなみに pairs から 4 を取り出すには、
gosh> (cdr (cdr (car pairs))) 4
このように car と cdr を組み合せればいいね。
1 や 7 を取り出すにはどうすればいいかな?
その他の数字はどうだろう?
いろいろな要素の取り出しを練習してみよう。
ペアとその要素の取り出し方について理解できたら次へすすもう。
でも・・・
「car と cdr を組み合せないと要素が取り出せないなんて、すごく面倒くさくない?」
「Scheme はリストを処理する言語だって言ってたけど car と cdr しかないの? ショボくない?」
と思ったそこの君!
Scheme はリストを処理する言語ですが、リストを操作する手続きは、
基本的に car と cdr しかありません! びっくりでしょ?w
それで十分な事を後で説明するので、もう少し待ってください。
空リスト
次にリストの話に戻る前に、空リストを考えておこう。
空リストというのは、そのまんまですが、要素が 1 つもない空っぽのリストのことです。
gosh> '() ()
空っぽのリストなんて何が嬉しいの? って思ったかも知れないけれども
Scheme でプログラミングする上で
・リストが空なのか? ・それとも空じゃないのか?
はとても重要な意味を持つので、今は謎かも知れないけれども覚えておいてください。
ペアとリスト(再)
では、リストの話に戻っていこう。ここまで長かった。
実はペアの要素としてリストも持つ事が出来ます!
gosh> (cons '(1 2 3 4 5) '(6 7 8 9 0)) ((1 2 3 4 5) 6 7 8 9 0) gosh> (cons '() '(1 2 3)) (() 1 2 3) gosh> (cons '() '()) (())
するどい人は表示結果からピンと来るかも知れないね。
これ覚えてるかな?
「リストとは、(要素 . リスト) で構成されるペアの再帰的構造を言う。」
まだなんのこっちゃかもしれないけど大丈夫。これから核心に迫っていくからね。
あえて cons で書いてみます。
gosh> (cons 1 '()) (1) gosh> (cons 1 (cons 2 '())) (1 2) gosh> (cons 1 (cons 2 (cons 3'()))) (1 2 3)
表示結果がリストみたいになってるのわかるかな?
説明上の理由で 3 2 1 の順で考えてみよう。
gosh> (cons 3 '()) (3)
3 と空リストでペアを作ると、3 を 1 つ要素に持つリストになります。
このリストにさらに cons で 2 を追加してみるよ。
gosh> (cons 2 (cons 3 '())) (2 3)
2 と 3 の要素を持つリストになったね。
さらに 1 を cons したらどうなるかな?
gosh> (cons 1 (cons 2 (cons 3 '()))) (1 2 3)
1, 2, 3 の 3 つの要素を持つリストが出来たね。
つぎは要素の取り出しをやってみよう。
cons で作ったリストを lst に define しておいて、
gosh> (define lst (cons 1 (cons 2 (cons 3 '())))) lst
gosh> lst (1 2 3)
1 を取り出すにはどうすればいい?
gosh> (car lst) 1
先頭の要素を取り出すのは car だったね。
cdr したらどうなると思う?
gosh> (cdr lst) (2 3)
こうなる。cdr は「先頭以外の要素を取り出す」だったね?
cdr した結果にさらに car するとどうだろう。
gosh> (car (cdr lst)) 2
car は先頭の要素を取り出すので 2 が拾えるね。
じゃあ、car を cdr に変えたらどうなるかな?
gosh> (cdr (cdr lst)) (3)
先頭以外の要素を取り出したね。
ここで取り出せるのは 3 じゃなくて、3 を 1 つ要素に持つリスト「'(3)」になっていることに注意しよう。
さらに 3 を取り出すにはどうすれば良いかな?
gosh> (car (cdr (cdr lst))) 3
car を使えばいいね。
じゃあ、car の代りに cdr にしたら何が取り出せるだろう?
gosh> (cdr (cdr (cdr lst))) ()
空リストを返しました。リストの要素が
1 つのとき、cdr を使うと空リストを取り出します。ここまでいいかな?
もう一度この文を思い出してみよう。
「リストとは、(要素 . リスト) で構成されるペアの再帰的構造を言う。」
ここまで説明すれば、この文の意味が理解できたと思うんだけど、どうかな?
さらに、リストは car と cdr を組み合せて、再帰呼び出しを使えば、各要素を順番に取り出すプログラムが書けそうだと思わない?
car と cdr だけで十分な気がしてこない? どうかな?
はい。ここでさらに話を
(goukei '(60 75 95 55 75))
まで戻します。goukei 手続き実装してみるよ。
(define (goukei lst) (if (null? lst) 0 (+ (car lst) (goukei (cdr lst)))))
いきなり答えを書いたけれども、いちいち細かい事を説明しなくても理解できるはず!
空リストの判断は null? 手続きを使います。
lst が空リストだったら 0 を返して終了だね。
空リストじゃないときは goukei の引数に (cdr lst) を渡して再帰呼び出ししつつ、
(car lst) で先頭の要素を拾いながら足し算していけばいいね。
ただし、このプログラムは要素がたくさんあるリストを処理しようとすると
動作がおかしくなるかもしれません。コンピュータの内部事情によるものなので
今は理由はわからなくても大丈夫です。
次回は動作がおかしくならない方法について説明する予定です。
つづく
