Comprehension problem with FD in core.logic

Showing 1-5 of 5 messages
Comprehension problem with FD in core.logic Stanislas Nanchen 4/29/13 12:03 PM
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.
Re: Comprehension problem with FD in core.logic David Nolen 4/29/13 12:22 PM
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.



--
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.
 
 

Re: Comprehension problem with FD in core.logic Stanislas Nanchen 4/29/13 1:29 PM
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.
Re: Comprehension problem with FD in core.logic Stanislas Nanchen 5/1/13 1:43 AM
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.
Re: Comprehension problem with FD in core.logic David Nolen 5/1/13 5:33 AM
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.