Search code examples
prologclpfd

Using a constrained variable with `length/2`


Here is the problem:

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.6-5-g5aeabd5)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- use_module(library(clpfd)).
true.

?- N in 1..3, length(L, N).
N = 1,
L = [_G1580] ;
N = 2,
L = [_G1580, _G1583] ;
N = 3,
L = [_G1580, _G1583, _G1586] ;
ERROR: Out of global stack % after a while

(I can switch the order of the subqueries, the result is the same).

I guess I need to label N before I can use it, but I wonder what the problem is? I have not managed to choke up length/2 before.


Solution

  • What's probably more useful than a slightly less nondeterministic length/2 is a proper list-length constraint. You can find an ECLiPSe implementation of it here, called len/2. With this you get the following behaviour:

    ?- N :: 1..3, len(Xs, N).
    N = N{1 .. 3}
    Xs = [_431|_482]               % note it must contain at least one element!
    There is 1 delayed goal.
    Yes (0.00s cpu)
    

    You can then enumerate the valid lists either by enumerating N:

    ?- N :: 1..3, len(Xs, N), indomain(N).
    N = 1
    Xs = [_478]
    Yes (0.00s cpu, solution 1, maybe more)
    N = 2
    Xs = [_478, _557]
    Yes (0.02s cpu, solution 2, maybe more)
    N = 3
    Xs = [_478, _557, _561]
    Yes (0.02s cpu, solution 3)
    

    or by generating lists with good old standard length/2:

    ?- N :: 1..3, len(Xs, N), length(Xs, _).
    N = 1
    Xs = [_488]
    Yes (0.00s cpu, solution 1, maybe more)
    N = 2
    Xs = [_488, _555]
    Yes (0.02s cpu, solution 2, maybe more)
    N = 3
    Xs = [_488, _555, _636]
    Yes (0.02s cpu, solution 3)