GEB MU puzzle in miniKanren

mu.scm

; Douglas Hofstadter's MU puzzle from Gödel, Escher, Bach
; written in miniKanren
; 
; https://github.com/miniKanren/miniKanren/blob/master/mk.scm

(load "mk.scm")

(define print
  (lambda (exp)
    (display exp)
    (newline)))

(define appendo
  (lambda (l s out)
    (conde
      [(== '() l) (== s out)]
      [(fresh (a d res)
         (== `(,a . ,d) l)
         (== `(,a . ,res) out)
         (appendo d s res))])))

(define muo
  (lambda (in out)
    (conde
      [(fresh (x)
        (appendo x `(I) in)
        (appendo x `(I U) out))]
      [(fresh (x xx)
        (== `(M . ,x) in)
        (== `(M . ,xx) out)
        (appendo x x xx))]
      [(fresh (x y)
        (appendo x `(I I I . ,y) in)
        (appendo x `(U . ,y) out))]
      [(fresh (x y)
        (appendo x `(U U . ,y) in)
        (appendo x y out))]
      [(fresh (tmp)
        (muo in tmp)
        (muo tmp out))])))

; (map print (run 5 (q) (muo '(M I) q)))
; (map print (run 5 (q) (muo '(M I U) q)))
; (map print (run 5 (q) (muo '(M U I I I U) q)))
; (map print (run 5 (q) (muo '(I I I) q)))
; (map print (run 5 (q) (muo '(M U U U) q)))
; (map print (run 20 (q) (muo '(M I) q)))
(map print (run 1 (q) (muo '(M I) '(M U))))