Schemeの継続を利用する例としてambオペレーター
未だに分かったようで分かってない
そもそも継続を使わないといけないものなのか、これは
あとfailの初期化がみんなわざわざ継続使ってなんか
やってるけどどうしてそんなことする必要があるのか
これは関数版 failの初期化も自己流
;; choose is function version for amb
(define *paths* '())
(define *nopath-sym* 'no-paths)
(define (fail)
(if (null? *paths*) (error *nopath-sym*)
((pop! *paths*))))
(define (choose . ls)
(if (null? ls) (fail)
(let/cc return
(push! *paths* (lambda () (return (apply choose (cdr ls)))))
(car ls))))
(define-syntax require
(syntax-rules ()
((_ b) (if (not b) (fail)))))グラフのパス探索でもしてみる
;; define of graph
(define vertexes '(0 1 2 3))
(define edges
'((0 . 1) (1 . 0) (0 . 2) (2 . 0)
(1 . 2) (2 . 1) (1 . 3) (3 . 1)
(2 . 3) (3 . 2)) )
(define (conj? u v)
(find (cut equal? <> (cons u v)) edges))
;; 任意の長さのuからvへのパスを探す
;; 同じ点を重複させると、深さ優先なので止まらない
;; 履歴を持たせて、同じ点は一度しか辿らせない
(define (reachable? u v)
(define (%r u his)
(if (conj? u v)
(list v)
(let1 w (apply choose vertexes)
(require (conj? u w))
(require (not (find (cut = w <>) his)))
(cons w (%r w (cons u his))) )))
(string-join (map x->string (cons u (%r u '()))) " -> ") )
;; no-paths エラーが出るまで fail させる
(define (all-paths u v)
(display (reachable? u v)) (newline)
(let while ()
(display (fail)) (newline)
(while) ))
; gosh> (all-paths 0 3)
; 0 -> 1 -> 3
; 0 -> 2 -> 3
; *** ERROR: no-paths
; (ry)2つは確かにパスを見つけられてるけど、長さ3のパスが見つけられない
0 -> 1 -> 2 -> 3
0 -> 2 -> 1 -> 3とかいうパスもあるのに
わからん