2008/12/31

【scheme】1.2.1＠SICP　再帰と反復と遅延演算

大晦日なのに、またまた階乗計算ですが。線形再帰と反復。 お陰で遅延評価（遅延演算）がわかったー！計算式の評価の前に式展開が先に行われるということなんだねと思う。以下、SICPよりほぼ写経ですが・・・。 一般的な階乗計算関数

;;factorial ;;n! = n * (n - 1) * (n - 2)....3 * 2 * 1
(define factorial
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))
(factorial 5);;=> 120
上記関数の実行イメージ
(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factoriall 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120
こっちの発想はなかった。 1*2*3・・・とやっていって、かける数がパラメータで与えられた回数に達するまで続ける方法。
;;n! = 1 * 2 * 3....
(define factorial2
  (lambda (n)
    (define iter
      (lambda (product counter)
        (if (> counter n)
          product
          (iter (* counter product) (+ counter 1)))))
    (iter 1 1)))

(factorial2 5);;=> 120
実行イメージ
(factorial2 5)
(iter 1 1 5)
(iter 1 2 5)
(iter 2 3 5)
(iter 6 4 5)
(iter 24 5 5)
(iter 120 6 5)
120
written by time: 0 件のコメント:
labels : ,

【scheme】クロージャ

よく見るクロージャのサンプルをSchemeで書いてみた。初期値を取って、呼ばれるたびにインクリメントした値を返す関数を返す関数。こういうの見るとOOPっているの？ってならないか。

(define counter 
  (lambda (n)
    (lambda ()
      (set! n (+ n 1)) n)))

(define disp
  (lambda (s)
    (display s)
    (newline)))

(let ((c (counter 0)))
  (disp (c));;=> 1
  (disp (c));;=> 2
  (disp (c));;=> 3
  (disp (c));;=> 4
  (disp (c)));;=> 5

(let ((c2 (counter 10)))
  (disp (c2));;=> 11
  (disp (c2));;=> 12
  (disp (c2));;=> 13
  (disp (c2)));;=> 14
written by time: 0 件のコメント:
labels :

【scheme】アキュムレータ、局所変数、破壊的代入

ハッカーと画家 コンピュータ時代の創造者たち http://stack.nayutaya.jp/book/4274065979 のP.198のアキュムレータを写経したり。

アキュムレータを生成する関数、すなわち、数nを取り、 「数iを取ってnをiだけ増加させ、その増加した値を返す関数」 を返すような関数だ（「増加させる」に注意。ただ足すだけではない。 アキュムレータ（累積機）だから累積させなければ）。

パラメータ：n 戻り値： パラメータ：i 戻り値：nをi増加させて返すを返す

;;=> accumulator
(define accumulator
  (lambda (n)
    (lambda (i)
      (set! n (+ n i)) n)))

;; local variable
(let ((a (accumulator 0)))
  (display (a 1))(newline);;=> 1
  (display (a 1))(newline);;=> 2
  (display (a 3))(newline);;=> 5
  (display (a 0))(newline));;=> 5

クロージャってことでいいよねコレ。ついでに、局所変数についても調べてみた。（let）

Schemeも破壊的代入を行う手続きが書けるんだね。（set!）

なんか違和感あるなー、なんとなく、代入って。 まぁ話によると、純粋な関数型言語ってHaskellとConcurrentCleanくらいしかないみたいだしね。（純粋関数型言語 ＝ 代入なしってこと？） こういうの（display, newline）が冗長だー。こういうのどう書くかなー。

(let ((a (accumulator 0)))
  (display (a 1))(newline);;=> 1
  (display (a 1))(newline);;=> 2
  (display (a 3))(newline);;=> 5
  (display (a 0))(newline));;=> 5
変数も代入もまだSICPに出てこない。 SICPってSchemeの入門書ではなくてプログラミングとかコンピュータ科学とかの入門書のはずだよな。一般的には変数とか代入が最初に解説してありそうなもんだけどねｗ変数や代入より関数定義、再帰、レキシカルスコープが先に出てくるんだもんなーｗ
written by time: 0 件のコメント:
labels :

【Scheme】問題1.6＠SICP

なぜ「if」が特殊形式なのか。「new-if」関数を定義して確かめてみるという問題。 実際やってみたけど、ピンとこなかった。（ちゃんとifの動作を思い出してればわかったはず）

;;not special syntax. new-if procidure.
(define new-if
  (lambda (predicate then-clause else-clause)
    (cond 
      (predicate then-clause)
      (else else-clause))))

(new-if (= 2 3) 0 5);;=> 5
(new-if (= 1 1) 0 5);;=> 0
こないだのsqrt内のgood-enough?で使われているifをnew-ifに置き換えるとエラー。ピンとこなかったのでまんまと解答集を見てみる。
(define square
  (lambda (x)
    (* x x)))

(define avarage
  (lambda (x y)
    (/ (+ x y) 2)))

;; "if" replaced "new-if"
(define sqrt
  (lambda (x)
    (define improve
      (lambda (guess)
        (avarage guess (/ x guess))))
    (define good-enough? 
      (lambda (guess)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess)
        (new-if (good-enough? guess)
          guess
          (sqrt-iter (improve guess)))))
    (sqrt-iter 1.0)))

(sqrt 9);;=> 3.00009155413138
そうだった。 ifはpredicateが真の場合は2つ目のパラメータを評価しないんだった。 new-ifではnew-ifが評価される前にsqrt-iterが評価されて無限再帰ですね。
written by time: 0 件のコメント:
labels : ,

【scheme】ブロック内スコープ＠SICP

平方根を求めるsqrt関数 先日のもの（【scheme】1.1.7 例：Newton法による平方根＠SICP）

(define avarage
  (lambda (x y)
    (/ (+ x y) 2)))
(avarage 10 20);;=> 15
(avarage 5.0 8.0);;=> 6.5

(define square
  (lambda (x)
    (* x x)))
(square 5);;=> 25
(square 12);;=> 144

(define improve
  (lambda (guess x)
    (avarage guess (/ x guess))))
(improve 10.0 5.0);;=> 5.25
(improve 1.5 2.5);;=> 1.5833333333333335

(define good-enough?
  (lambda (guess x)
    (< (abs (- (square guess) x)) 0.001)))

(define sqrt-iter
  (lambda (guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x))))

(define sqrt
  (lambda (x)
    (sqrt-iter 1.0 x)))

(sqrt 9);;=> 3.00009155413138
(sqrt (+ 100 37));;=> 11.704699917758145
(sqrt (+ (sqrt 2)(sqrt 3)));;=> 1.7739279023207892
(square (sqrt 1000));;=> 1000.000369924366
各関数をsqrt定義内に納めたもの。

;; local scope difinition
(define sqrt
  (lambda (x)
    (define square
      (lambda (x)
        (* x x)))
    (define avarage
      (lambda (x y)
        (/ (+ x y) 2)))
    (define improve
      (lambda (guess x)
        (avarage guess (/ x guess))))
    (define good-enough?
      (lambda (guess x)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess x)
        (if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x) x))))
    (sqrt-iter 1.0 x)))
(sqrt 9);;=> 3.00009155413138
sqrtのパラメータxのブロック内スコープ（レキシカルスコープ）を利用したもの。 xを利用した関数を返すようにすればクロージャできそうでつね。

(define square
  (lambda (x)
    (* x x)))
(define avarage
  (lambda (x y)
    (/ (+ x y) 2)))

(define sqrt
  (lambda (x)
    (define improve
      (lambda (guess)
        (avarage guess (/ x guess))))
    (define good-enough?
      (lambda (guess)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess)))))
    (sqrt-iter 1.0)))
(sqrt 9);;=> 3.00009155413138
written by time: 0 件のコメント:
labels : ,

2008/12/30

【scheme】スコープ＠ブロック（？）

ブロック内スコープとレキシカルスコープか。

(define x
  (lambda ()
    (define y "Hello world")
    (define z
      (lambda ()
        (display y)))
    (z)))
(x);;=> Hello world
;;(y);;=> reference to undefined identifier: y
;;(z);;=> reference to undefined identifier: z
written by time: 0 件のコメント:
labels :

【scheme】こないだのlistで書き忘れた

リストの中身を全部出力したかっただけなんだけどな。こんなことになっちゃった。センスなさすぎﾜﾛﾀ系？

;;list
(define x (list 1 2 3))

;;display list
(define disp-list
  (lambda (l)
    (if (not (null? l))
      (begin
        (display (car l)) 
        (newline)
        (disp-list (cdr l))))))

(disp-list x)
;;=> 1
;;=> 2
;;=> 3
written by time: 0 件のコメント:
labels :

2008/12/29

【scheme】listとcarとcdr

(define x (list 1 2 3))
x;;=> (1 2 3)

(car x);;=> 1
(cdr x);;=> (2 3)

(define y '(1 2 3))

y;;=> (1 2 3)
(car y);;=> 1
(cdr y);;=> (2 3)
written by time: 0 件のコメント:
labels :

2008/12/28

【scheme】コラッツcollatz角谷

「schemeでもコラッツの問題を書いてみよう！」と思ったら、こないだ書いててﾜﾛﾀ。 消しゴム系ですね、頭ん中。
【Scheme】SchemeでもCollatz http://ameblo.jp/valvallow/entry-10179274699.html
これがこないだの。 
(define (collatz n)
  (display n)
  (newline)
  (if (> n 1)
      (if (even? n)
          (collatz (/ n 2))
          (collatz (+ (* n 3) 1)))))

(collatz 5)
;; =>  5
;; =>  16
;; =>  8
;; =>  4
;; =>  2
=> 1
(collatz 30)
;; =>  30
;; =>  15
;; =>  46
;; =>  23
;; =>  70
;; =>  35
;; =>  106
;; =>  53
;; =>  160
;; =>  80
;; =>  40
;; =>  20
;; =>  10
;; =>  5
;; =>  16
;; =>  8
;; =>  4
;; =>  2
;; =>  1
これが今日書いたの。 こないだより悪くなってるような気がするな。
;;collatz
(define collatz
  (lambda (seed f)
    (f seed)
    (cond
     ((<= seed 1))
     ((even? seed)
      (collatz (/ seed 2) f))
     ((odd? seed)
      (collatz (+ 1 (* seed 3)) f)))))

(collatz 5 (lambda (s)(display s)(newline))) ;;=> 5 ;;=> 16 ;;=> 8 ;;=> 4 ;;=> 2 ;;=> 1 ;;=> #t

Y-Combinatorで。
 【Scheme】Y-Combinator（Yコンビネータ/不動点演算子） http://ameblo.jp/valvallow/entry-10182574504.html 
;;collatz with y-combinator

;;Y is y-combinator
(define Y
  (lambda (f)
    ((lambda (h)(h h))
     (lambda (p)
       (f (lambda (n)((p p) n)))))))

;;collatz
(define collatz
  (lambda (f)
    (lambda (seed)
      (display seed)
      (newline)
      (cond
       ((<= seed 1))
       ((even? seed)
        (f (/ seed 2)))
       ((odd? seed)
        (f (+ 1 (* seed 3))))))))

((Y collatz) 5)
;;=> 5
;;=> 16
;;=> 8
;;=> 4
;;=> 2
;;=> 1
;;=> #t
Y-Combinator、複数パラメータに対応したの書いてみたい。 ここが参考になりそう。
ボクノス：Yコンビネータを読み解こう http://d.hatena.ne.jp/tanakaBox/20080203/1202023473

プログラミングGauche
written by time: 0 件のコメント:
labels :

【scheme】解答集＠SICP（計算機プログラムの構造と解釈）

こんなページを発見。
訳者直々の解答集ということでいいのかな？

計算機プログラムの構造と解釈
written by time: 0 件のコメント:
labels : ,
登録: 投稿 (Atom)