You might also be interested in some of the linear-time or near-linear unification algorithms from Huet, Paterson & Wegman, and Martelli & Montanari. With that, you might also be interested in the Conchon & Filliâtre persistent union-find structure. The persistent union-find should give the advantage of a union-find based solution without the full cost of backtracking that David rightly warns against. Dan and I played with some of this a while back, and I think our experimental versions are still up on github somewhere.
Best, JBH On Thu, Mar 16, 2017 at 6:35 PM, David Kahn <[email protected]> wrote: > Keep in mind that in minikanren you are constantly forking the > substitution at every conde. Any simplifications you make to the > substitution won't affect siblings branches on the search tree, and have to > be re-applied. For something like type inference which needs no > backtracking it should work great; but anything that does backtrack will > just be slowed down. This is just something you have to live with in fair > search, but can be somewhat gotten around by making a depth-first search > version of conde for problems where you aren't worried about divergence. > > > On Monday, February 6, 2017 at 7:26:16 PM UTC-6, Paulo César Cuneo wrote: >> >> Hi minikanren list! >> >> I was implementing my own version of minikanren in clojure and i figure >> out i could interleave walk with unifiy, so i could flatten out lvars chain. >> Beside the current version isnt tail recursive (and may stackoveflow), >> see any problem. >> I guess cache may missbehave, but lvars are not compacted together, soo i >> dont know. >> Is there a minikanren benchmark test anywhere? >> Someone already tried this? >> >> >> (defn unify [x y a] >> (cond >> (lvar? x) (let [x' (get-var a x) >> ;; get-var is not walk >> a' (if (lvar? x') >> (if (= x x') >> (ext-s a x' y) >> (unify x' y a)) >> (unify y x' a)) >> x'' (get-var a' x')] >> ;; compress path >> (ext-s a' x x'')) >> (or (seq? x) >> (seq? y)) (unify-seq x y a) >> (= x y) a >> :else nil)) >> >> Bye. >> > -- > You received this message because you are subscribed to the Google Groups > "minikanren" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/minikanren. > For more options, visit https://groups.google.com/d/optout. > -- JBH -- You received this message because you are subscribed to the Google Groups "minikanren" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/minikanren. For more options, visit https://groups.google.com/d/optout.
