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?