Scheme 手習い（８）

第9章：…… もう一度、もう一度、もう一度、……

keep-looking

(define (pick to lat)
  (cond [(= to 0) (car lat)]
        [else (pick (- to 1) (cdr lat))]))
        
(define (keep-looking a to lat)
  (cond [(number? to)
         (keep-looking a (pick to lat) lat)]
        [else (eq? a to)]))

引数のインデックスの要素が数字かシンボルかを判定する。 数字だった場合にはさらにその数字をインデックスとして要素を取得して同じ事を繰り返す。もし、シンボルだったら渡された a と一致するかを調べる関数。

この再帰は常にリストが短くなっていくわけではないので、無限ループする可能性がある。

これを「不自然な再帰」と呼んでいる。

eternity

(define (eternity x)
  (eternity x))

値を返さない関数。このような関数を部分関数というらしい。 入力に対して一部しか値が定義されないから部分関数と呼ぶのか？

shift

(define (build a b)
  (cons a (cons b '()))) 
(define (first a)
  (car a))
(define (second a)
  (car (cdr a)))
 
(define (shift x)
  (build (first (first x))
    (build (second (first x))
      (second x))))

第１要素がペアであるペアをとり、第２要素に第１要素の先頭をつけてペアを作る関数

align

(define (align para)
  (cond [(atom? para) para]
        [(a-pair? (first para))
         (align (shift para))]
        [else (build (first para)
                (align (second para)))]))

ペアで構成されたリストを整列させる関数。 たとえば ((a b) ((c d) (e f))) という入力の場合、出力は (a (b (c (d (e f))))) となる。

length* と weight*

(define (length* para)
  (cond [(atom? para) 1]
        [else (+ (length* (first para))
                 (length* (second para)))]))
(define (weight* para)
  (cond [(atom? para) 1]
        [else (+ (* (length* (first para)) 2)
                 (length* (second para)))]))

ペアで構成されたリストの要素を数える関数。 また、第一要素に重みをつけたのが weight* 関数。

weight* を使うと align が再帰するたびに、重みが軽くなっていることが分かるので、再帰が収束することが分かるらしい。 なんとなく理屈は理解できるけど、すべてのケースに置いて本当にそうなのかは不明。

C

(define (C n)
  (cond [(one? n) 1]
        [(even? n) (C (/ n 2))]
        [else (C (add1 (* 3 n)))]))

いわゆるコラッツ問題の関数。 この関数はすべての引数に対して値を返すかどうかはまだ分かっていない。

A

(define (A n m)
  (cond [(zero? n) (add1 m)]
        [(zero? m) (A (sub1 n) 1)]
        [else (A (sub1 n)
                 (A n (sub1 m)))]))

アッカーマン関数。 コラッツ問題と違いこの関数は全関数（必ず値を返す）ことが分かっているらしい。 ただし、計算量が膨大なため計算機では計算に時間がかかり現実的な時間で計算できないことが多い。

will-stop?

与えられた関数が停止するかどうかを調べられる関数 will-stop? が存在するかどうかを問う思考実験。

(define (last-try x)
  (and (will-stop? last-try) (eternity x)))

will-stop? が存在すると仮定して、上記のような関数を定義する。

last-try が停止すると仮定した場合、(will-stop? last-try) は true となる。 すると、(eternity x) が評価され、結果として (last-try x) は (eternity x) によって停止しない関数となってしまい、仮定と矛盾する。

一方、last-try が停止しないと仮定した場合、(will-stop? last-try) は false となる。 (last-try x) は false となるため (eternity x) は評価されずに停止してしまうので、仮定と矛盾する。

結果として、will-stop? が存在するという仮定が間違いだったことが分かる。

いわゆる停止性問題。

Y コンビネータ

この章の残りは、リストの要素数を数える length を使って Y コンビネーターについて説明している。 長くなるので、それは次回に。