関数型言語の勉強にSICPを読もう - (33) 3章 - 標準部品化力、オブジェクトおよび状態 (152-155ページ)
問題3.18
最初の要素を保持しておく。
要素をたどっていって終端までたどり着いたら循環は存在しない。
最初の要素と eq? なものが見つかれば循環が存在する。
ところで下のコードの front ですが、constant(readonly)にするにはどうしたらよいんでしょうか。
絶対に set! されないぜという安心感があると堅牢になる気がします。
;; こちらはデバッグ版
(define (list-have-cycle? l)
(let ((front (car l)))
(define (check e)
(cond ((null? e) #f) ;; have no cycle
((eq? #?=front #?=(car e)) #t) ;; have cycle
(else (check (cdr e)))))
(check (cdr l))))
;; デバッグをはずしたもの
(define (list-have-cycle? l)
(let ((front (car l)))
(define (check e)
(cond ((null? e) #f) ;; have no cycle
((eq? front (car e)) #t) ;; have cycle
(else (check (cdr e)))))
(check (cdr l))))
;; have cycle?
(define a (cons 'x 'x))
(set-cdr! a a)
(display (list-have-cycle? a))
(newline)
;; have no cycle?
(define b (list 'I 'have 'a 'pen))
(display (list-have-cycle? b))
(newline)
追記
g:sicp:id:hyukiさんからコメントを頂きました。
この方法だと途中から循環している場合に対応できませんので、frontではなく一つ一つ要素を記憶していき memqで調べるほうがよさそうです。
参考:http://sicp.g.hatena.ne.jp/hyuki/20060514/cyclic
問題3.19
3.18を一定量のスペースしか使わないアルゴリズムを使って再実装しなければいけない。
引数で渡されるリストの長さに依存しないという意味だと思うんだけど、うーんうーん。
すくなくとも終端っぽいところまでたどり着かないと無理なような気がする。
ギブアップ。
問題3.20
パス
問題3.21
queue, dequeueなどの構造はさすがに何回も触れたことがあるので（ほかの部分と比べて)簡単に感じます。
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
(define (empty-queue? queue) (null? (front-ptr queue)))
(define (make-queue) (cons '() '()))
(define (front-queue queue)
(if (empty-queue? queue)
(error "empty queue")
(car (front-ptr queue))))
(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
(cond ((empty-queue? queue)
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else
(set-cdr! (rear-ptr queue) new-pair)
(set-rear-ptr! queue new-pair)
queue))))
(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "empty queue"))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))
(define (display-queue queue)
(define (display-queue-internal q)
(cond ((eq? q (rear-ptr queue))
(display " ")
(display (car q)))
(else
(begin (display " ")
(display (car q))
(display-queue-internal (cdr q))))))
(if (empty-queue? queue)
(display "empty queue\n")
(begin
(display "(")
(display-queue-internal (front-ptr queue))
(display ")\n"))))
;; make-queue test
(define q1 (make-queue))
(display-queue q1)
;; empty queue
(insert-queue! q1 'a)
(display-queue q1)
;;( a)
(insert-queue! q1 'b)
(display-queue q1)
;;( a b)
(delete-queue! q1)
(display-queue q1)
;;( b)
(delete-queue! q1)
(display-queue q1)
;; empty queue
計算機プログラムの構造と解釈
posted with amazlet on 06.04.15
Gerald Jay Sussman Julie Sussman Harold Abelson 和田 英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404
