Infinite loop with `counto` relation in core.logic

72 views Asked by At

I am interested in expressing the number of occurrences of an element in a list as a relational goal in Clojure's core.logic library.

(Note that this question is not a duplicate of clojure core.logic counting elements in a set because that question was accepting non-relational goals as an answer.)

In particular, I am adapting the following Prolog code to core.logic.

count(_, [], 0).
count(X, [X | T], N) :-
  !, count(X, T, N1),
  N is N1 + 1.
count(X, [_ | T], N) :-
  count(X, T, N).

Here is my attempt

(defn counto [item coll n]
  (l/conde
   ;; If the coll is empty, the count must be 0.
   [(l/emptyo coll)
    (l/== n 0)]
   ;; If the coll head matches the item, increment count and recur.
   [(l/fresh [tail n*]
      (l/conso item tail coll)
      (counto item tail n*)
      (fd/+ n* 1 n))]
   ;; If the coll head does not match the item, retain count and recur.
   [(l/fresh [head tail]
      (l/conso head tail coll)
      (l/!= head item)
      (counto item tail n))]))

This seems to work well for generating a tiny amount of inputs. e.g.

(l/run 3 [q]
  (l/fresh [x y z]
    (l/== q [x y z])
    (fd/in x y z (fd/interval 0 1))
    (counto 0 q 2)))

;; => ((1 0 0) (0 1 0) (0 0 1))

However, this code runs into an infinite loop when requesting for additional solutions. e.g. replacing 3 with 4 above, or even replacing l/run with l/run*, results in an infinite loop.

Is there a mistake in my implementation? Or am I hitting a limitation of core.logic?

0

There are 0 answers