Sat Jun 29 13:16:47 JST 2013

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

とかいうパスもあるのに

わからん