;;; List operations for YAQ83 after Clocksin-Mellish.
;;;
;;; Antti J Ylikoski 12-14-2010.
;;;
;;; Written to test the Common LISP YAQ.


;;; The only sensible thing to do with this size of a program is to
;;; put it in its own package, to avoid a hyperzillion name conflicts.

(defpackage :yaq
  (:use :common-lisp))

(in-package :yaq)



(eval-when (compile eval load)
  (load "C:\\yaq83\\yaq83.lsp"))

(defpred last
    ((last ?x (?x)))
    ((last ?x (?ignore . ?y))
     (last ?x ?y)))


(defpred delete
    ((delete ?x (?x . ?l) ?l))
    ((delete ?x (?y . ?l1) (?y . ?l2))
     (delete ?x ?l1 ?l2)))

(defpred append
    ((append nil ?x ?x))
    ((append (?x . ?y) ?z (?x . ?u))
     (append ?y ?z ?u)))

(defpred member
    ((member ?x (?x . ?y)))
    ((member ?x (?a . ?y))
     (member ?x ?y)))

(defpred rev
    ((rev ?l1 ?l2)
     (rev0 ?l1 () ?l2)))

(defpred rev0
    ((rev0 (?x . ?l) ?l2 ?l3)
     (rev0 ?l (?x . ?l2) ?l3))
    ((rev0 () ?l ?l)))

(defpred naive-reverse
    ((naive-reverse () ()))
    ((naive-reverse (?h . ?t) ?l)
     (naive-reverse ?t ?z)
     (append ?z (?h) ?l)))

;;; Quicksort with YAQ.

(defpred split
    ((split ?h (?a . ?x) (?a . ?y) ?z)
     (=< ?a ?h)
     (split ?h ?x ?y ?z))
    ((split ?h (?a . ?x) ?y (?a . ?z))
     (> ?a ?h)
     (split ?h ?x ?y ?z))
    ((split ?ignore () () ())))

(defpred quisort
    ((quisort () ()))
    ((quisort (?h . ?t) ?s)
     (split ?h ?t ?a ?b)
     (quisort ?a ?a1)
     (quisort ?b ?b1)
     (append ?a1 (?h . ?b1) ?s)))