kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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という変数を導入した

翻訳(最終版)

関数を関係に翻訳するには、まずdefinedefrelに置き換える。次に、ひとつひとつのcond行をunnestし、condcondeに置き換える。#t#sに、#f#uにunnnestする。
もし1行以上のcond行が真偽以外の値を返すときは、関数の値を保持するために引数(例えばout)を追加する。真偽以外の値を持つ行をunnestするときは、outに値を結びつけるか、out再帰の最後の引数になるようにせよ。

末尾再帰になるように、ってことかな?
引数の場所まで影響する?

上の定義ではfreshは必要最小限のスコープ(っていうのかな)で使われてるけど
これをひとまとめにすると、carocdroconsoにまとめることができる

(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はプロパーなリストでも値を持つ、ってとこからつながってるんだろうな
何かポイントなのかここ