Reasoned Schemer (80) listo

3. Seeing Old Friends in New Ways

Translationの続きだけどTranslationよりも再帰が出てきたことに注目して

(defrel (listo l)
  (conde ((nullo l))
         ((fresh (d) (cdro l d) (listo d)))))

> (run* x (listo `(a b ,x d)))
'(_0)

1周目はTranslationするところだけ見てたので
今回は動きを見てみる
まずどんなstreamができているのか

> ((listo `(a b ,x d)) empty-s)
'(((#(d))
   (#(a) . d)
   (#(d) d)
   (#(a) . #(x))
   (#(d) #(x) d)
   (#(a) . b)
   (#(d) b #(x) d)
   (#(a) . a)))

defrelを元に戻すとかなりだ

> (((((((((((((((((listo `(a b ,x d)) empty-s))))))))))))))))
'(((#(d))
   ...
   (#(a) . a)))

あれ
でもdが()だったり'dだったりしてない？
aも

いいのか
fresh (d)のdだから何度も出てきて全部別モノか
再帰してる順番にassociationができてるんだな

詳細は適当にはしょりながら追っかける

  ((listo `(a b ,x d)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(a b ,x d) d) (listo d)) empty-s) ; -> a = 'a, d = `(b ,x d)
= ((listo `(b ,x d)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(b ,x d) d) (listo d)) empty-s) ; -> a = 'b, d = `(,x d)
= ((listo `(,x d)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(,x d) d) (listo d)) empty-s) ; -> a = x, d = `(d)
= ((listo `(d)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(d) d) (listo d)) empty-s) ; -> a = d, d = '()
= ((listo '() empty-s)
= ((conde ...) empty-s)
= ((nullo '()) empty-s)
= '(())

(())に各再帰で発生したassociationをconjしていくとできあがりってわけだな
だいたいわかった

(run* x (listo ``(a b c . ,x)))はno value
なんでだ
さっきと同じ流れで((nullo x) empty-s)になってxが()になりそうに見える

違うとするとその前のcondeだな

  ((listo `(a b c . ,x) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(a b c . ,x) d) (listo d)) empty-s) ; -> a = 'a, d = `(b c . ,x)
= ((listo `(b c . ,x)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(b c . ,x) d) (listo d)) empty-s) ; -> a = 'b, d = `(c . ,x)
= ((listo `(c . ,x)) empty-s)
= ((conde ...) empty-s)
= ((conj (cdro `(c . ,x) d) (listo d)) empty-s) ; -> a = c, d = x
= ((listo x) empty-s)
= ((conde ((nullo x))
          ((fresh (d) (cdro x d) (listo d)))) empty-s)

ここだ
xが()のときはsucceedだけどそれだけじゃなくて
((fresh (d) (cdro x d) (listo d)))が成功するならなんでもいいんだ
っていうのがこれか

> (run 5 x (listo `(a b c . ,x)))
'(() (_0) (_0 _1) (_0 _1 _2) (_0 _1 _2 _3))

1周目にやったことをすっかり忘れているの図
condeなんだから複数の可能性があることを忘れちゃいかんな