>
>第３回
>に出席してきました。議論はまあともかく、ちょっと進行は遅い気も？ でもこんなものかなあ。
>
>置き換えモデルについてはあまり上手い説明ができなかったのは悔やまれます。あれはさ、ラムダ計算と同じで(っていうかラムダ計算なんですが)、プログラムスタックとかは関係ない計算モデルのお話なんですよ。関数呼出しだからといって何もスタックに積むわけじゃないわけで、ただ粛々を字面を置き換えていくだけで計算が進行していくというモデルなわけです。プログラミングの知識がかえって邪魔をしている例なのかなーと思っていました。あとはまあ、 Shiro さんの「
>なんでも再帰
>」があると……逆に混乱するかな。ポイントなのは末尾再帰ではなくて末尾呼出しでも上手く行くということなのですが。
>
>ところで今回の話題の問題 1.11 ですが、これは Haskell で書けば、
>
>fs = 0 : 1 : 2 : zipWith3 (\a b c -> 3 * a + 2 * b + c) fs (tail fs) (tail (tail fs))
f n = fs !! n
>
>とでもなるでしょうか。これは繰返し的な構造をもったアルゴリズムです。 scheme だと
>
>(define fs (cons 0 (cons 1 (cons 2 (map (lambda (a b c) (+ (* 3 a) (* 2 b) c)) fs (cdr fs) (cddr fs))))))
(define (f n) (list-ref fs n))
>
>ですが、これをやると止まらなくなるので問題があります。Haskell では本質的にはリストはストリームなのでこういう書き方が簡単に出来るわけですねー(くだらん自慢か)。
>
>あと Pascal 三角形もこんな感じですね。
>
>pascalTriangle = iterate nextLine [1]
where nextLine l = zipWith (+) (l ++ [0]) (0 : l)
pt l x = pascalTriangle !! l !! x
>
>これもリストの評価が遅延されることを生かしていますが、実際には pt で l が決定されたときに l の高さのパスカル三角形を構成すれば同じことなので no problem です。
>
>(define (iterate n x f)
(if (= n 0)
(cons x '())
(cons x (iterate (- n 1) (f x) f))))
(define (pt l x)
(define (next-line l) (map + (append l '(0)) (cons 0 l)))
(define pascal-triangle (iterate l '(1) next-line))
(list-ref (list-ref pascal-triangle l) x))
>
>とまあこんな感じ？
>
>ただまあどっちにせよ、この本のこの段階ではリストが登場しないのでこういう書き方しちゃいけません。
>
