I'm trying to wrap my head around CLP(FD). Here's a simple example of where I'm not sure of the most idiomatic approach. Suppose we have a List of numbers (L), with some numbers already filled, like this.
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
And I want to say something like, the numbers both left and right of a fixed one must sum up that number. A possible solution for the above, would be:
L = [0, 0, 1, 3, 0, 1, 1, 4, 2, 0, 2, 0]
There are, of course, other solutions. My first approach would be something like:
Append both lists;sum/3, constrain the resulting list to be #= to the pivot.Would this be ideomatic? Am I missing something more evident?
Level 2. I think the predicate sum/3 does most of the work. Let's change the problem a little bit:
A continuous string of 1's to the left and right of the pivot must sum up to the pivot.
So given this:
L = [_, _, _, 3, _, _, _, 5, _, _, 2, _]
A possible solution would be:
L = [0, 0, 0, 3, 1, 1, 1, 5, 1, 1, 2, 0]
And now it's trickier... I would say something along the lines of, the appended left and right sublists of pivot N must contain a sublist of 1's of length N. Does this make sense? How would I say something along those lines using CLP(FD)?
Your reasoning is perfectly correct and will work.
Nevertheless, it falls short in a critical aspect: Your description is currently very imperative, and if you implement this in the way you describe, then you will be able to solve given instances, but you will not be able to use the same program to generate such puzzle instances.
Let me explain in more detail what I mean.
We start with the representation of such puzzles. You are currently using:
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
This is called a defaulty representation because you cannot cleanly distinguish the different cases. If you think logically, and think of this is an "instance" of the puzzle, then any more special case of this term must be regarded as a more specific case of the instance, for example a partial or complete solution. But in this representation, that's not the case, because instantiating one of the arguments further suddenly turns it into a completely different instance instead of only a more specific manifestation.
So, here is a clean representation of such puzzles:
example([?,?,?,p(3),?,?,?,p(4),?,?,p(2),?]).
Here, I am distinguishing the two possible cases by different terms. I am using:
? for unknown integersp(P) to denote the pivot element P.Many other representations are possible, and if you need to express variable sharing, you could for example use i(I) to represent an unknown integer I. The point is that you can distinguish the cases by pattern matching instead of non-monotonic constructs that test for instantiations. This is the key to general solutions that can be used in all directions.
Let us reconsider the imperative description you gave:
Now let us express this declaratively. We must avoid imperatives like "search", "get" and "append", because these all imply a particular direction of use.
A declarative description could look like this: We are describing triples of the form Lefts-Pivot-Rights, where the following holds:
The sum of integers
LeftsandRightsis equal toPivot.
If we manage to write a Prolog program that describes such triples and draws a suitable connection from task instances to such triples, then we're done and can use it in all directions.
It's fun to work on clean representations, and we can easily convert them to other forms because we can so easily distinguish the cases. Therefore, let us convert the instances to triples now, over which we can reason more easily.
Let us reflect the task representation: It is a list of elements. Very often when describing lists in Prolog, DCG notation (dcg) comes in handy. So, let us describe tasks and at the same time describe the relation between task description and triples:
is_p_is([Ls|Rest]) -->
is(Ls),
is_p_is_(Rest).
is_p_is_([Pivot,Rs]) --> [p(Pivot)], is(Rs).
is_p_is_([Pivot,Rs,Rs|IPIs]) -->
[p(Pivot)],
is(Rs),
is_p_is_(IPIs).
is([]) --> [].
is([_|Is]) --> [?], is(Is).
This DCG is the key point of the whole answer.
Here is how you can use it, to see what it describes:
?- example(Es), phrase(is_p_is(Ls), Es). Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?], Ls = [[_G902, _G905, _G908], 3, [_G920, _G923, _G926], [_G920, _G923, _G926], 4, [_G938, _G941], [_G938, _G941], 2, [_G950]] ; false.
From this, you see that I have eliminated the complex reasoning of "searching what is where and how far". Instead, it's a simple and general relation between instances and lists of the form:
[Left0,Pivot0,Right0,Left1,Pivot1,Right1,Left2,...]
where the "triples" are implicit and can be grouped as follows:
[(Left0,Pivot0,Right0),(Left1,Pivot1,Right1),...]
and further, Rightn is the same as Leftn+1.
Given such lists, posting the CLP(FD) constraints is straight-forward:
constraints([]).
constraints([Left,Pivot,Right|Rest]) :-
Left ins 0..sup,
Right ins 0..sup,
sum(Left, #=, SL),
sum(Right, #=, SR),
Pivot #= SL + SR,
constraints(Rest).
If you want, you could use append/3 here, but why even bother? Using append/3 incurs some risk of introducing non-termination, whereas CLP(FD) constraints (ideally) always terminate, so I am using two sum/3 constraints instead.
Extracting the variables is also straight-forward:
variables([]) --> [].
variables([Left,_,Right|Rest]) -->
seq(Left),
seq(Right),
variables(Rest).
seq([]) --> [].
seq([L|Ls]) --> [L], seq(Ls).
Here is an example query and a few answers:
?- example(Es), phrase(is_p_is(Ls), Es), constraints(Ls), phrase(variables(Ls), Vs), label(Vs). Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?], Ls = [[0, 0, 0], 3, [0, 0, 3], [0, 0, 3], 4, [0, 1], [0, 1], 2, [1]], Vs = [0, 0, 0, 0, 0, 3, 0, 0, 3, 0, 1, 0, 1, 1] ; Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?], Ls = [[0, 0, 0], 3, [0, 0, 3], [0, 0, 3], 4, [1, 0], [1, 0], 2, [1]], Vs = [0, 0, 0, 0, 0, 3, 0, 0, 3, 1, 0, 1, 0, 1] ; Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?], Ls = [[0, 0, 0], 3, [0, 1, 2], [0, 1, 2], 4, [0, 1], [0, 1], 2, [1]], Vs = [0, 0, 0, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 1] ; etc.
I have highlighted the "triple" representation.
Now the crucial point: All of this is completely general, and we can use it to generate the instances themselves!
Example:
?- length(Es, _), phrase(is_p_is(Ls), Es). Es = [p(_G874)], Ls = [[], _G874, []] ; Es = [p(_G877), ?], Ls = [[], _G877, [_G885]] ; Es = [p(_G877), p(_G888)], Ls = [[], _G877, [], [], _G888, []] ; Es = [?, p(_G880)], Ls = [[_G877], _G880, []] ; Es = [p(_G880), ?, ?], Ls = [[], _G880, [_G888, _G891]] .
This is a natural by-product of thinking in terms of relations, and using clean representations.
I leave the more specific second question as the first exercise for you. I hope the principles shown above help you to arrive at a clean and general solution that lets you extract the utmost advantage of logic programming.
As the second exercise, I leave rewriting the above to use the i(_) representation for unknown integers. With such a representation, we could get rid of several disadvantages in the above. For example, extracting the variables would become somewhat more convenient:
variables([]) --> [].
variables([L|Ls]) -->
variable_(L),
variables(Ls).
variable_(i(I)) --> [I].
variable_(p(_)) --> [].
Example:
?- phrase(variables([i(X),p(3),i(Y)]), Vs). Vs = [X, Y].
Also, we would not needlessly duplicate the remaining variables in such lists.
Further, check this out:
?- length(Ls, _), phrase(variables(Ls), Vs). Ls = Vs, Vs = [] ; Ls = [i(_2066)], Vs = [_2066] ; Ls = [p(_2066)], Vs = [] ; Ls = [i(_2072), i(_2082)], Vs = [_2072, _2082] ; Ls = [i(_2072), p(_2082)], Vs = [_2072] ; Ls = [p(_2072), i(_2076)], Vs = [_2076] .
How does this pure relation compare with using impure predicates like exclude/3? Can you also generate all possible cases with it? See logical-purity for more information.
As the third and last exercise, I leave the toughest one: Reread what I wrote and find all instances where I am, by using imperative wording, not doing justice to the generality of what is actually implemented, and reword it so that it reflects the actual situation.
I give an example: I say "Extracting the variables", and what could be more natural, right? But I have actually implemented a full-fledged relation between variables and triples, and you can use it to:
For example, we can use the most general query:
?- phrase(variables(Ts), Vs). Ts = Vs, Vs = [] ; Ts = [[], _1960, []], Vs = [] ; Ts = [[], _1960, [], [], _1978, []], Vs = [] ; Ts = [[], _1960, [], [], _1978, [], [], _1996, []], Vs = [] .
That's of course not a very fair enumeration, but it goes well beyond extracting something, because nothing at all is even given in the query.
So, to answer your question: In my view, we regard as most idiomatic Prolog those solutions which most impressively exhibit the declarative properties we expect from relations and unique advantages of logic programs, such as:
An elegant, idiomatic Prolog solution often starts with a clean representation of instances, and descriptive predicate names.