tree-walkと高階関数

高階関数とは、関数自体を引数にしたり戻り値（って言っていいのかな）にしたりする関数のこと。
7章2節の冒頭に出てくるfor-eachは関数を引数にとる高階関数。

僕はこの高階関数が弱点のようで、以下のtree-walk関数の動きがなかなか理解できなかった。

(define tree-walk
  (lambda (walker proc l)
    (walker (lambda (e) (if (list? e)
                            (tree-walk walker proc e)
                            (proc e)))
            l)))

引数にtree-walkを適用した結果が以下。

gosh> (tree-walk map (lambda (n) (* 2 n)) '(0 (1) ((2)) (((3)))))
(0 (2) ((4)) (((6))))

だね。
どこが理解できなかったかって言うと、ネストしたリスト構造が保存される理由。

ってことで、自分の頭の整理という意味も込めて、

(tree-walk map (lambda (e) e) '(a (b) ((c)))

の評価の様子を書いておく。
ネストしたリスト構造が保存される様子のみに着目するため、procにあたる関数は引数をそのまま返す関数にしておく。

まず、ネストしていない関数の場合を考えてみる。

(tree-walk map (lambda (e) e) '(a b c))

ネストしていないので、全ての要素でif式の式は

(proc e)

になる。要するに、

(map (lambda (e) e) '(a b c))

と同じことをしている。
んで、最終的に値は

(a b c)

になるわけだ。戻り値はネストしていない3つの要素からなるリストで、つまり引数と同じ構造をしている。

では、問題の

'(a (b) ((c)))

に対する適用について考える。
まず、

a

はアトムなので問題ない。つぎにアクセスするS式は

(b)

で、ネストしているので再帰して、

(tree-walker map (lambda (e) e) '(b))

を求めることになって、これは先ほどやったネストしていない状態なので、

(b)

という値が帰ってくる。
最後に、

((c))

に関しては、ネストしているので再帰する。

(tree-walk map (lambda (e) e) '((c)))

これはさらにネストしているので、

(tree-walk map (lambda (e) e) '(c))

を求めることになる。これはさっきの

(b)

の時と同じなので

(c)

が返る。ってことで、

(tree-walk map (lambda (e) e) '((c)))

の値は

((c))

ってことになる。で、

(tree-walk map (lambda (e) e) '(a (b) ((c))))

の値は、これら3つをまとめて

(a (b) ((c)))

ってなるんですわな。
確かに、ネストの構造がそのまま保存されてるな。