Scheme事始め13:数学的な例を関数を作りながらみてみる(2)

  • ペアノ的自然数定義。1を0,1,2,...個要素とするリスト vの操作として表すsuccessorのsucc,predecessorのpred
    • consは1を先頭に付け加えること、cdrは先頭を除くこと
> (define succ
     (lambda (v)
       (cons 1 v)))
    
> (define pred
    (lambda (v)
      (cdr v)))
> (succ ())
. #%app: missing procedure expression;
 probably originally (), which is an illegal empty application in: (#%app)
> (succ '())
(1)
> (succ (succ '()))
(1 1)
> (succ (succ (succ '())))
(1 1 1)
> (pred '(1 1 1 1))
(1 1 1)
> (pred (pred '(1 1 1 1)))
(1 1)
> (pred (pred (pred '(1 1 1 1))))
(1)
> (pred (pred (pred (pred '(1 1 1 1)))))
()
> (pred (pred (pred (pred (pred '(1 1 1 1))))))
. . mcdr: contract violation
  expected: mpair?
  given: ()
  • x+yx+1y-1をペアにして、yが0になるまで繰り返す、と考えると以下が加算処理になる
> (define plus
    (lambda (x y)
      (if (null? y)
          x
          (succ (plus x (pred y))))))
> (plus '(1 1) '(1 1 1))
(1 1 1 1 1)
    • 1のリストを整数値に返るとすると、"null?"のチェックを"zero?"にして「足す1」「引く1」の関数をsucc,predに換えればよい
> (define add1
    (lambda (x)
      (+ x 1)))
> (add1 0)
1
> (define sub1
    (lambda (x)
      (- x 1)))
> (sub1 4)
3
> (define plus-num
    (lambda (x y)
      (if(zero? y)
         x
         (add1 (plus-num x (sub1 y))))))
> (plus-num 3 4)
7
    • 1のリストとして表したものを数値にするときに、関数の骨格は変わらなかった。もう一度1のリストに戻して、今度は、数値にするのではなくて演算を加算から乗算にすることにする。0を足したらxは変わらない、と言う点は、0をかけたら0になる、と書きかえる必要がある。0より大きい自然数をかけるのは、xをy回連結する、と見る
> (define mult
    (lambda (x y)
      (if(null? y)
         '()
         (plus x (mult x (pred y))))))
> (mult '(1 1) '(1 1 1))
(1 1 1 1 1 1)
    • 乗算はy回の加算だった。べき乗はy回の乗算だ、と見れば:0乗は1なので
> (define pows
    (lambda (x y)
      (if(null? y)
         '(1)
         (mult x (pows x (pred y))))))
> (pows '(1 1) '(1 1 1))
(1 1 1 1 1 1 1 1)
  • 再帰部分を独立させる
    • 加算処理を次のように書き直す
> (define plus
    (lambda (x y)
      (if(zero? y)
         x
         (+ 1 (plus x (- y 1))))))
> (plus 3 4)
7
    • よく見ると、再帰部分が(+1 (plus (-y 1)))となっていて、plusという関数の再帰の中に、plusという関数と1を足す、という関数が入っていることがわかる
    • これを変えるのにもう一つ変数を持ち込むと、次のようになる。yを減らすたびにpを増やして、最後にx+pをしている、ということで、そんなことなら最初からx+yをすればいいだろう、という感じだが、ここでは、「計算の構造」のことを考えるため、ということで、その点は無視します。こうすると、yを減らしながら、計算を表すリストの入れ子を深くする代わりに、yとpの値の間でバーターをするだけにできるという(メモリ上の)メリットがあるし、再帰関数が純化しているというメリットもある
    • 再帰部分を純化して、最後にやりたいことを実現する方法ともいえるが、この方法を末尾再帰形式と言うそうだ
> (define plus2
    (lambda (x y p)
      (if(zero? y)
         (+ x p)
         (plus2 x (- y 1) (+ p 1)))))
> (plus2 3 4 0)
7