Reasoned Schemer (009) appendoと翻訳(最終版)
4. Double Your Fun
何が2倍?
(define (append l t)
(cond
((null? l) t)
(#t (cons (car l) (append (cdr l) t)))))
l
がプロパーなリストだと値を持たないけれども
t
はプロパーなリストでも値を持つ
ということを気にしている?
(defrel (appendo l t out)
(conde
((nullo l) (== t out))
((fresh (res)
(fresh (d)
(cdro l d)
(appendo d t res))
(fresh (a)
(caro l a)
(conso a res out))))))
- 今まで出てきた関数と違って、真偽ではなくいろんな値を返す
- そのために
out
という変数を導入した
翻訳(最終版)
関数を関係に翻訳するには、まずdefine
をdefrel
に置き換える。次に、ひとつひとつのcond
行をunnestし、cond
をconde
に置き換える。#t
は#s
に、#f
は#u
にunnnestする。
もし1行以上のcond
行が真偽以外の値を返すときは、関数の値を保持するために引数(例えばout
)を追加する。真偽以外の値を持つ行をunnestするときは、out
に値を結びつけるか、out
が再帰の最後の引数になるようにせよ。
末尾再帰になるように、ってことかな?
引数の場所まで影響する?
上の定義ではfresh
は必要最小限のスコープ(っていうのかな)で使われてるけど
これをひとまとめにすると、caro
とcdro
をconso
にまとめることができる
(defrel (appendo l t out)
(conde
((nullo l) (== t out))
((fresh (a d res)
(conso a d l)
(appendo d t res))
(conso a res out))))))
なるほど
(run 6 x (fresh (y z) (appendo x y z)))
の値は
(()
(_0)
(_0 _1)
(_0 _1 _2)
(_0 _1 _2 _3)
(_0 _1 _2 _3 _4))
だけれども
(run 6 y (fresh (x z) (appendo x y z)))
の値は
(_0
_0
_0
_0
_0
_0)
っていう話は、l
がプロパーなリストだと値を持たないけれども
t
はプロパーなリストでも値を持つ、ってとこからつながってるんだろうな
何かポイントなのかここ