Fork me on GitHub
#core-logic
<
2021-11-08
>
tschady18:11:53

My first core.logic program. i’m trying to have lvars be values in a map of known keys. This code doesn’t seem to run the membero functions. Any help? I only have m at runtime, so I can’t just hardcode in 2 logic vars, m could have 100 keys for instance. I think the problem is in the for .. Also, any other advice very welcome.

(def m {:a [[1 2 3]
            [2 100 200]]
        :b [[1 2 3]
            [2 3 4]]})

(run* [q]
  (let [result-map (zipmap (keys m) (repeatedly lvar))]
    (for [k (keys m)
          vs (get m k)]
      (membero (get result-map k) vs))
    (fd/distinct (vals result-map))
    (== q result-map)))
; => ({:a _0, :b _1})

paulocuneo19:11:39

minikanren is an inmutable lang/framework. goals will not be evaluated as logic relations outside run*, this means the goals inside let expression have no effect, only the last goals of let is passed into run*, this means only the last goal from the let body is evaluated. additionally, functional expression will not be evaluated as relations, this means is not posible to use a (functional) for expression, you will need to re-write the for in a relational way ( Disclaimer: I'm not an expert, nor a english native speaker 😄 )

tschady19:11:17

very helpful, thanks!

paulocuneo19:11:08

https://github.com/clojure/core.logic/blob/master/src/main/clojure/clojure/core/logic.clj#L1281 and* will come in handy to transform the seq returned by the for expresion into a goal/relation https://github.com/clojure/core.logic/blob/master/src/main/clojure/clojure/core/logic.clj#L1276 all can combine the goals inside let body into a goal something like

(def m {:a [[1 2 3]
            [2 100 200]]
        :b [[1 2 3]
            [2 3 4]]})

(run* [q]
  (let [result-map (zipmap (keys m) (repeatedly lvar))]
    (all (and* (for [k  (keys m)
                     vs (get m k)]
                 (membero (get result-map k) vs)))
         (fd/distinct (vals result-map))
         (== q result-map))))
must say this is quite hackish, there should be a relational way to express what you want

tschady19:11:52

just did my own before comparing, works:

tschady19:11:56

(def m {:a [[1 2 3]
            [2 100 200]]
        :b [[1 2 3]
            [2 3 4]]})

(defn member-all [var possibles]
  (and* (map #(membero var %) possibles)))

(let [vars (repeatedly (count (keys m)) lvar)]
  (apply zipmap
         (keys m)
         (run 1 [q]
           (and* (map #(member-all % %2) vars (vals m)))
           (fd/distinct vars)
           (== q vars))))

tschady19:11:59

tho this depends on keys/vals of map always returning in same order

tschady19:11:49

thanks for the help, changed my thinking. i’ll keep at it.

tschady20:11:55

getting better, moved out the let and got rid of the for:

(def m {:a [[1 2 3]
            [2 100 200]]
        :b [[1 2 3]
            [2 3 4]]})

(defn member-all [var possibles]
  (and* (map #(membero var %) possibles)))

(let [result-map (zipmap (keys m) (repeatedly lvar))]
  (run* [q]
    (and* (map (fn [[k vs]] (member-all (get result-map k) vs)) m))
    (distincto (vals result-map))
    (== q result-map)))

tschady20:11:42

this is super slow on large input btw

hiredman20:11:20

membero is not fast

hiredman20:11:51

It can be hard to give big o measurements of logic programs, because of how abstract they can be, but membero is basically o(n) of the collection

hiredman20:11:05

And you are doing it over and over again

paulocuneo20:11:31

maybe the nail doesnt fit the hammer, dont know a better way to phrase it are you planning to run the query backwards?

tschady20:11:09

stupid nail! swing harder.

😆 1
tschady20:11:26

i don’t know what “run the query backwards” means

paulocuneo20:11:14

relational programs can calculate the inputs given an output, it's like running it backwards

hiredman20:11:57

It might speed things up to move distincto up(very non-relational to care about ordering, but it might prune the search tree earlier)

tschady20:11:33

wow @U0NCTKEV8 went from 86s -> 8s with distincto first. I restarted CIDER in between, so shouldn’t be any caching.

hiredman20:11:06

I guess the membero is basically growing the search tree exponentially everytime, only for distincto to come along and prune most of it, putting distincto first means most the branches created by membero are immediately pruned

tschady22:11:42

down to 95ms by reducing the multiple memberos per key to one with a set/intersection, good enough

tschady22:11:47

thanks y’all

hiredman22:11:24

a great addition to to core.logic would be a clp(set) implementation

tschady18:11:58

btw, I replaced (and* (map with (everyg