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)))
ってなるんですわな。
確かに、ネストの構造がそのまま保存されてるな。