■
授業で久しぶりにschemeを触ったので、備忘録として。
授業ではscheme48って言うのを使ったんだけど、
ボクの知ってるschemeと若干処理系が違ったらしい。
first→car
rest→cdr
empty→nil, '()
ってなってた。
(define (list-sum list)
(cond ((null? list) 0)
(else (+ (car list) (list-sum (cdr list))))))
って書くよね。
これは、
(i)リストが空の時、0を返す。
(ii)それ以外のときは、リストの最初の数+ 残りのリストの合計値
で再帰していく形なわけだ。
末尾再帰関数で書きなおすと、
(define (sum-iter list)
(define (calc sum list)
(cond
*1 (cdr list)))))
(calc 0 list))
となる。
これは、局所関数calcが
(i)リストが空の時、持っている合計値(sum)を返す。
(ii)それ以外のとき、再帰でcalcを呼び出す。このとき、sum= sum + リストの最初の値 list = 最初の値を除いた残りのリスト となる。
それで、sum-iterに与えられたリストに対して、sum=0でcalcを呼び出して、繰り返し処理をしているわけだ。
例 list = '(1 2 3 4) のとき。
1回目 sum = 0 , list='(1 2 3 4)
2回目 sum = 1 , list='(2 3 4)
3回目 sum = 3 , list='(3 4)
4回目 sum = 6 , list='(4)
5回目 sum = 10 list='()
普通の再帰関数と違うのは、戻り値での計算が無いこと。
普通の場合、 リストの最初の値＋再帰関数の戻り値
ってなってるけど、
末尾再帰関数だと、最後は戻り値だけで返ってくるから早い。
その分のメモリを確保する必要が無いわけだ。
まぁ、高速化するときはこっちを使ったほうがいいんだっけ？
もう一つ、高階関数。
授業でやったのはこんな感じだった
(define (double func)
(lambda (x) (func (func x))))
これを使って
((double add1) 0) #2
ってできたりする。
高階関数を使って、関数を返す関数を作ったわけですね。
いやー、それにしてもscheme面白いね・ω・
*1:null? list) sum) (else (calc (+ sum (car list
