SICP 読み (125) 3.5.1 ストリームは遅延リスト

うーん。なんかワケワカな勘違い。いや、ナチュラルなのか。

問題 3.50

まず、通勤バスの中で map を机上で書いてみた。

(define (map p . l)
  (if (null? (car l))
      '()
      (cons (apply p (map car l))
	    (apply map (cons p (map cdr l))))))

で、自宅環境で試すもループしているクサい。よく見りゃたしかに微妙。ハマりつつも以下のようなソレをでっち上げた。未だに正しいのかどうか分からん。

(define (map1 p items)
  (if (null? items)
      '()
      (cons (p (car items))
	    (map1 p (cdr items)))))

(define (map2 p . l)
  (if (null? (car l))
      '()
      (cons (apply p (map1 car l))
	    (apply map2 (cons p (map1 cdr l))))))

以下の試験はパスしてます。

#!/usr/bin/env gosh

(use test.unit)
(require "3.5.1")

(define-test-suite "3.5.1"

  ("map"
   ("test of map"
    (assert-equal '(741 852 963)
		  (map2 + (list 1 2 3) (list 40 50 60) (list 700 800 900)))
    (assert-equal '(9 12 15)
		  (map2 (lambda (x y) (+ x (* 2 y)))
			(list 1 2 3)
			(list 4 5 6)))
    (assert-equal '(1 4 9 16)
		  (map2 (lambda (x) (* x x)) (list 1 2 3 4)))
    (assert-equal '(1 4 9 16)
		  (map1 (lambda (x) (* x x)) (list 1 2 3 4)))
    )
   )
  )

うーん ....

これを応用すれば良いはずなんで問題の解は以下なカンジでしょうか。

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
	      (cons proc (map stream-cdr argstreams))))))

これを確認するために、define-syntax を今から調べます。

define-syntax と delay と cons-stream

こんなので良いのだろうか。すげぇ適当。以下にセットで定義。

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

(define-syntax delay
  (syntax-rules ()
    ((_ p) (memo-proc (lambda () p)))))

(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define (force delayed-object) (delayed-object))
(define (memo-proc p)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (if (not already-run?)
	  (begin (set! result (p))
		 (set! already-run? #t)
		 result)
	  result))))

しかも define-syntax はドタマで宣言ってか定義されていないと駄目とゆー事に気がつくまで当分時間がかかりました。ってか、delay ってデフォルトで手続きが定義されてるし (駄目
さらに、stream-map がリストを戻すという致命的なナチュラル勘違いで何故に以下の試験にパスしない、と (以下略

  ("stream-map"
   ("sample 1"
    (assert-equal '(1 4 9 16)
		  (stream-map (lambda (x) (* x x))
			      (stream-enumerate-interval 1 4)))
    )
   )

勘違いの仕方が無茶苦茶だなぁ、と思いつつ以下の試験にはパスしている模様。

  ("stream-map"
   ("sample 1"
    (let ((s (stream-map (lambda (x) (* x x))
			 (stream-enumerate-interval 1 4))))
      (assert-equal 1 (stream-car s))
      (assert-equal 4 (stream-car (stream-cdr s)))
      (assert-equal 9 (stream-car (stream-cdr (stream-cdr s))))
      (assert-equal 16 (stream-car (stream-cdr (stream-cdr (stream-cdr s)))))
      )
    )
   )

これ、他の手続きも試験作って確認した方が良さげ。考え方が全然違うのでナチュラル率が格段に上がってたりします。

追記

エントリを逆に見ていて書いてないコトがある事に気付きました。_特殊形式_なソレをスルーして p.190 あたりまでの手続きを書いて gosh 上で動作させてループのような動作を確認しております。このあたりで前の前のエントリにある「特殊形式」に気がついた次第で。（とほほほ
以降の問題はこのあたりも含め、きちんと理解できてないと大変だろう、と思ってはいるのですが (以下略