Comprehension problem with FD in core.logic

[Stanislas Nanchen]

Hi everyone,

I'm playing with FD in core.logic and have problem to understand the behavior of the following relation.

(defne weighted-listo [l w]

  ([() _] (fd/== w 0))

  ([[h . t] _]

    (fresh [n]

           (fd/in n (fd/interval 0 java.lang.Integer/MAX_VALUE))

           (fd/in h (fd/interval 1 java.lang.Integer/MAX_VALUE))

           (fd/+ h n w)

           (weighted-listo t n))))

The relation asserts that the list 'l' contains positive integers and that their sum is 'w'.

So as expected:

==> (run* [q] (weighted-listo [1 1 2] 4))

returns

<== (_0)

Now when, I use the relation to generate lists with weight 4, the list [1 1 2] does not appear:

==> (run* [q] (weighted-listo q 4))

<== ((4) (1 3) (2 2) (3 1) (1 2 1) (2 1 1) (1 1 1 1))

Can someone explain me, why the list [1 1 2] is not generated?

Thanks,

Stan.

[David Nolen]

I think we probably need a new goal - label. This goal will specify that some sequence term should fully enumerate any FD Vars contained therein. It will not be recursive. This seems in line with what is supported by SWI-Prolog's CLP(FD) functionality.

Ticket created: http://dev.clojure.org/jira/browse/LOGIC-133

--
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 minikanren+...@googlegroups.com.
To post to this group, send email to minik...@googlegroups.com.
Visit this group at http://groups.google.com/group/minikanren?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Stanislas Nanchen]

I found an idea on Stackoverflow http://stackoverflow.com/questions/9875760/sum-of-elements-in-list-in-prolog

The code becomes the following:

(defmacro in-pos [& vars]

  `(fd/in ~@vars (fd/interval 1 java.lang.Integer/MAX_VALUE)))

(defne weighted-listo2 [l w]

  ([() _] (fd/== w 0))

  ([[h . ()] _] (in-pos h) (fd/== w h))

  ([[h1 h2 . t] _]

    (fresh [w2 l2]

           (in-pos h1)

           (in-pos h2)

           (fd/+ h1 h2 w2)

           (conso w2 t l2)

           (weighted-listo2 l2 w))))

it generates all the possibilities at the price of looping searching for the ninth.

[Stanislas Nanchen]

swi-prolog with label gives the whole result.

:- use_module(library(clpfd)).

weighted_list([], 0).

weighted_list([H|T], W) :-

H #>= 1,

H #=< W,

H + N #= W,

weighted_list(T, N),

label([H, N]).

:- weighted_list(X, 4).

X = [4] ;

X = [3, 1] ;

X = [2, 2] ;

X = [1, 3] ;

X = [2, 1, 1] ;

X = [1, 2, 1] ;

X = [1, 1, 2] ;

X = [1, 1, 1, 1] ;

false.

Without label, SWI prolog actually "finds" all the solutions:

X = [4] ;

X = [_G4851185, _G4851188],

clpfd:in(_G4851185, ..(1, 3)),

clpfd: #=(_G4851185+_G4851188, 4),

clpfd:in(_G4851188, ..(1, 3)) ;

X = [_G4852225, _G4852228, _G4852231],

clpfd:in(_G4852225, ..(1, 2)),

clpfd: #=(_G4852225+_G4852256, 4),

clpfd:in(_G4852256, ..(2, 3)),

clpfd: #=(_G4852228+_G4852231, _G4852256),

clpfd:in(_G4852228, ..(1, 2)),

clpfd:in(_G4852231, ..(1, 2)) ;

X = [1, 1, 1, 1] ;

false.

[David Nolen]

Yes that's what I'd expect, I'll play around with this some more. It may make sense to change core.logic's behavior to follow this behavior.