Hi all,
I've just implemented insertion sort with core.logic:
--8<---------------cut here---------------start------------->8---
(declare inserto)
(defn isorto
"A relation where sl is a sorted version of the list l."
([l sl]
(isorto l () sl))
([l acc sl]
(conde
[(== l ()) (== acc sl)]
[(fresh [f r nacc]
(conso f r l)
(inserto f acc nacc)
(isorto r nacc sl))])))
(defn cconso
"A relation where consing s and then f to r gives l."
[f s r l]
(fresh [l1]
(conso s r l1)
(conso f l1 l)))
(defn inserto
"A relation where inserting x into l gives the sorted list nl."
[x l nl]
(conde
[(== l ()) (== nl (list x))]
[(fresh [f r nf nr]
(conso f r l)
(conso nf nr nl)
(conde
[(fd/> x f) (== f nf) (inserto x r nr)] ;; fd is an alias for
clojure.core.logic.fd
[(fd/<= x f) (cconso x f r nl)]))]))
--8<---------------cut here---------------end--------------->8---
That works fine in forwards direction
--8<---------------cut here---------------start------------->8---
(run* [q]
(isorto (list 5 3 4 1 2) q))
;=> ((1 2 3 4 5))
--8<---------------cut here---------------end--------------->8---
and as a check
--8<---------------cut here---------------start------------->8---
(run* [q]
(isorto (list 3 2 1 4 5) (list 1 2 3 4 5)))
(_0)
--8<---------------cut here---------------end--------------->8---
but won't terminate in backwards direction
--8<---------------cut here---------------start------------->8---
(run* [q]
(isorto q (list 1 2 3)))
;; wait until hell freezes
--8<---------------cut here---------------end--------------->8---
where it ideally would unify q with all six possible permutations of the
sorted list (1 2 3). It doesn't even terminate when I provide the empty
list or a one-element list as the sorted list sl.
Well, actually I don't need all permutations. One would suffice which
could even be the sorted variant, i.e., in "backwards mode" I'd be happy
if it just unified l with sl.
I've tried partially replacing condes with condas or condus in various
combinations of the three occurrences but I only get to two different
outcomes. Either it doesn't terminate just as the all-conde version, or
it terminates without any answer.
I think at least inserto should be pretty correct and reversible, at
least I can ask it for all element/list pairs which would complete to a
given sorted list when inserting at the right position.
--8<---------------cut here---------------start------------->8---
(run* [q a]
(inserto q a (list 1 2 3 4 5)))
;=> ([1 (2 3 4 5)] [2 (1 3 4 5)] [3 (1 2 4 5)] [5 (1 2 3 4)] [4 (1 2 3 5)])
--8<---------------cut here---------------end--------------->8---
(Interesting that the 5 comes before the 4. Does that give any clue?)
Do I have some error in the code which I don't see anymore after staring
at the code for more than an hour? Or do I need to use some trick to
get it somehow reversible?
Bye,
Tassilo
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
