結城浩のSICP日記 RSSフィード

2006-05-05

継続の練習(1) 継続の練習(1) - 結城浩のSICP日記 を含むブックマーク

なんでも継続を斜め読みしました。

再帰版。自分の理解を確かめながら半・写経。

(define a '((a . b) (c . d) . e))
(define (leaf-count tree)
  (cond ((pair? tree)
          (+ (leaf-count (car tree))
             (leaf-count (cdr tree))))
        (else 1)))
(leaf-count a) ;=> 5

継続渡し形式(continuation passing style)版。自分の理解を確かめながら半・写経。引数のprocは「結果を送る先」ということですね。引数がcar-nとcdr-nになっているのは理解を確かめるため。

(define a '((a . b) (c . d) . e))
(define (leaf-count tree)
  (define (count tree proc)
    (cond ((pair? tree)
           (count (car tree)
            (lambda (car-n)
              (count (cdr tree)
                (lambda (cdr-n) (proc (+ car-n cdr-n)))))))
          (else (proc 1))))
  (count tree (lambda (result) result)))
(leaf-count a) ;=> 5

最後の結果を受け取るための関数で、うっ、と詰まったが、(lambda (result) result)にしてみました。いちおう動いているようです。

shiroさんの文書では「一引数の関数ならなんでも良いが、単純にvaluesを渡してやることで、最後に呼ばれるcontがそのままその値を返すようにしてやることができる」と書かれていたので、これでよいかな、と思っています。valuesを渡した場合には多値を返すのも自由自在という理解。

[]第5回 第5回 - 結城浩のSICP日記 を含むブックマーク

Scheme演習 第5回の問1を解きました。

Password を持つ銀行口座を作成せよ

(以下、問題文省略)

素直に書きました。

(define (call-the-cops) "You're under arrest.")
(define (make-account amount password)
  (define error-count 0)
  (define (change-amount! value)
    (set! amount value)
    amount)
  (define (withdraw value)
    (cond ((< amount value) "Insufficient funds")
          ((< value 0) "Invalid value")
          (else (change-amount! (- amount value)))))
  (define (deposit value)
    (cond ((< value 0) "Invalid value")
          (else (change-amount! (+ amount value)))))
  (define (dispatch command value)
    (cond ((equal? command 'withdraw) (withdraw value))
          ((equal? command 'deposit) (deposit value))
          (else "incorrect command")))
  (define (password-error)
    (set! error-count (+ error-count 1))
    (cond ((>= error-count 3) (call-the-cops))
          (else "incorrect password")))
  (define (password-ok) (set! error-count 0))
  (lambda (pass command value)
    (cond ((equal? pass password)
            (password-ok)
            (dispatch command value))
          (else (password-error)))))
(define acc (make-account 10000 'password))

(acc 'password 'withdraw 3000)
;=> 7000

(acc 'password 'withdraw 10000)
;=> Insufficient funds

(acc 'password 'deposit 1000)
;=> 8000

(acc 'wrong 'withdraw 5000)
;=> incorrect password

(acc 'password 'withdraw 5000)
;=> 3000

(acc 'wrong 'withdraw 1000)
;=> incorrect password

(acc 'pass 'deposit 1000)
;=> incorrect password

(acc 'word 'withdraw 1000)
;=> You're under arrest.

疑問:スタイルとして、引数と状態を表す変数をどう区別するのがよいか。

識別子とピリオド 識別子とピリオド - 結城浩のSICP日記 を含むブックマーク

R5RSの「識別子」を読んでいます。

識別子の厳密なルールは処理系依存。R5RSの以下の文章で、that begins ...に三人称単数現在形のsが付いているので、beginsの主語はa sequence of ...ですね。

The precise rules for forming identifiers vary among implementations of Scheme, but in all implementations a sequence of letters, digits, and ``extended alphabetic characters'' that begins with a character that cannot begin a number is an identifier. In addition, +, -, and ... are identifiers.

extended alphabetic charactersにはピリオドが含まれているが、ピリオドで始まって数字と理解されてしまう文字列は識別子になれない、と理解。

(define .5 "half")
;=> Compile Error: syntax-error: (define 0.5 "half")

(define .8. "number 8")
;=> .8.

.8.
;=> number 8

(define .. "parent")
;=> ..

..
;=> parent

ふむふむ。

In addition, +, -, and ... are identifiers.

↑のように明示的に書いてあるので ... は識別子として使える。

(define ... "Dots")
;=> ...

...
;=> Dots

ふむふむ。

要素が見つかるまでの部分リスト 要素が見つかるまでの部分リスト - 結城浩のSICP日記 を含むブックマーク

id:naoya_tさんの問題:

リストの先頭から、探している item が最初に見つかる場所までの部分リスト

naoya_tさんの解を見ずにチャレンジ。

まずは素朴に。

(define a '(1 2 3 4 5 6 7 8 9))

(define (cut-tail-1 lst item)
  (if (null? lst)
      lst
      (if (equal? (car lst) item)
          '()
          (cons (car lst) (cut-tail-1 (cdr lst) item)))))

(cut-tail-1 a 7)  ;=> (1 2 3 4 5 6)
(cut-tail-1 a 10) ;=> (1 2 3 4 5 6 7 8 9)

イテレータを使って。

(define a '(1 2 3 4 5 6 7 8 9))
(define (cut-tail-2 lst item)
  (define (cut-tail-iterator revhead item tail)
    (if (null? tail)
        (reverse revhead)
        (if (equal? item (car tail))
            (reverse revhead)
            (cut-tail-iterator (cons (car tail) revhead) item (cdr tail)))))
  (cut-tail-iterator '() item lst))

(cut-tail-2 a 7)    ;=> (1 2 3 4 5 6)
(cut-tail-2 a 10)   ;=> (1 2 3 4 5 6 7 8 9)

ここまで書いてnaoya_tさんの解を見る。そうか、イテレートした後reverseすればいいのか…。

コメント欄にあったhiratchさんの「中間結果のリストを生成したら負け」というフレーズに、ふむふむ。

よしっ、それなら…。

(define (cut-tail-3! lst item)
  (define (cut-tail-iterator! lst item tail)
    (if (null? (cdr tail))
        lst
        (if (equal? (cadr tail) item)
            (begin
              (set-cdr! tail '())
              lst)
            (cut-tail-iterator! lst item (cdr tail)))))
  (if (null? lst)
      lst
      (if (equal? (car lst) item)
          '()
          (cut-tail-iterator! lst item lst))))

(cut-tail-3! '(1 2 3 4 5 6 7 8 9) 1)    ;=> ()
(cut-tail-3! '(1 2 3 4 5 6 7 8 9) 7)    ;=> (1 2 3 4 5 6)
(cut-tail-3! '(1 2 3 4 5 6 7 8 9) 10)   ;=> (1 2 3 4 5 6 7 8 9)

尻尾を切り捨ててはいかんか…(^_^;

SRFI-27疑似乱数発生器インタフェース SRFI-27疑似乱数発生器インタフェース - 結城浩のSICP日記 を含むブックマーク

shiroさんから教えていただいたSRFI-27: Sources of Random Bitsを試します。「ランダムビットのソース」としてちゃんとGaucheのマニュアルにも載っていました。

まずは、デフォルトの乱数発生源を用いる場合。

(use srfi-27)

(random-source-pseudo-randomize! default-random-source 314159 265358)
(random-integer 1000) ;=> 356
(random-integer 1000) ;=> 686
(random-integer 1000) ;=> 793

(random-real) ;=> 0.7874209480319674
(random-real) ;=> 0.45651510801265416
(random-real) ;=> 0.9846236986553446

乱数発生源を作って使う場合。

(use srfi-27)

(define s (make-random-source))
(random-source-pseudo-randomize! s 314159 265358)

(define f (random-source-make-integers s))
(f 1000) ;=> 356
(f 1000) ;=> 686
(f 1000) ;=> 793

(define g (random-source-make-reals s))
(g) ;=> 0.7874209480319674
(g) ;=> 0.45651510801265416
(g) ;=> 0.9846236986553446