Prolog create list of lists

Question

I'm having some (or a lot of) trouble with lists of lists in prolog.

So I have a list of numbers, say [5,6,1,3] as input. The output should be [[5,25],[6,36],[1,1],[3,9]].

I already have a predicate that 'return's the 2 item lists (keep in mind that I'll have to change the get_squared_pair function to get some other relevant value):

get_squared_pair(Number, Result) :-
get_squared_value(Number, SquareValue),
Result = [Number, SquareValue].

get_squared_value(Number, Result) :-
Result is Number * Number.

Until here it's pretty logical. Now I need a predicate that recursively iterates though a list, adds the squared pair to a new list, and then returns this lists of lists. What I have right now is:

return_list([], 0).
return_list([Head | Tail], Result) :-
get_squared_pair(Head, Add),
append(Add,Result),
return_list(Tail, Result).

This doesn't work for a number of reasons, and it's mostly because I can't seem to figure out how the recursion actually works with lists, much less lists of lists. Also it's currently running in the wrong order which doesn't help.

I understand this might be a bit vague but I've tried googling my way out of this one but can't seem to translate what I find into my own problem very well.

Any help would be much appreciated!

Prolog does not have functions that define operations. It has predicates that define relations. They aren't the same thing. — lurker
Excellent point, and I'm still very new to prolog so forgive my ignorance. I did put a predicate tag on this post from the start, but I forgot to also reflect this in the actual text... too caught up in old habits! — freefall

lurker lurker · Accepted Answer · 2015-04-10T11:20:22

Let's look at your get_squared_pair/2 first. Although it's working, it can be tidied up a bit which will also help understand how Prolog works. The primary mechanism of Prolog is unification, which is not the same as assignment which occurs in other languages. In unification, Prolog examines two terms and attempts to unify them by instantiating variables in one or both of the terms to make them match. There are some predicates in Prolog, like is/2 which are used to evaluate expressions in one argument, and then unify the first argument with that result.

Your first predicate, then, which you have written as:

get_squared_pair(Number, Result) :-
    get_squared_value(Number, SquareValue),
    Result = [Number, SquareValue].

get_squared_value(Number, Result) :-
    Result is Number * Number.

Can be simplified in two ways. First, you can consolidate the get_squared_value/2 since it's just one line and doesn't really need its own predicate. And we'll rename the predicate so it's not imperative.

square_pair(Number, Square) :-
    S is Number * Number,     % Square the number
    Square = [Number, S].     % Unify Square with the pair

Prolog can unify terms in the head of the clause, so you can avoid the redundant unification. So this is all you need:

square_pair(Number, [Number, Square]) :-
    Square is Number * Number.

On to the main predicate, return_list/2. First, we'll rename this predicate to square_pairs. When doing recursion with lists, the most common pattern is to continue reducing a list until it is empty, and then a base case handles the empty list. Your implementation does this, but the base case is a little confused since the 2nd argument is an integer rather than a list:

square_pairs([], 0).

This really should be:

square_pairs([], []).

Your main predicate clause isn't making correct use of append/2. There are two forms of append in SWI Prolog: append/2 and append/3. You can look up what these do in the SWI Prolog online documentation. I can tell you that, in Prolog, you cannot change the value of a variable within a predicate clause once it's been instantiated except through backtracking. For example, look at the following sequence that might be in a predicate clause:

X = a,    % Unify X with the atom 'a'
X = b,    % Unify X with the atom 'b'

In this case, the second expression will always fail because X is already unified and cannot be unified again. However, if I have this:

foo(X),    % Call foo, which unifies X with a value that makes 'foo' succeed
bar(X, Y), % Call bar, which might fail based upon the value of 'X'

In the above case, if bar(X, Y) fails, then Prolog will backtrack to the foo(X) call and seek another value of X which makes foo(X) succeed. If it finds one, then it will call bar(X, Y) again with the new value of X, and so on.

So append(Add, Result) does not append Add to Result yielding a new value for Result. In fact, append with two arguments says that the second list argument is the concatenation of all the elements of the first list, assuming the first argument is a list of lists, so the definition of append/2 doesn't match anyway.

When thinking about your recursion, realize that the argument lists are in one-to-one correspondence with each other. The head of the result list is the "square pair" for the head of the list in the first argument. Then, recursively, the tail of the 2nd argument is a list of the square pairs for the tail of the first argument. You just need to express that in Prolog. We can also use the technique I described above for unification within the head of the clause.

square_pairs([Head | Tail], [SqPair | SqTail]) :-
    square_pair(Head, SqPair),
    square_pairs(Tail, SqTail).
square_pairs([], []).

Now there's another simplification we can do, which is eliminate the square_pair/2 auxiliary predicate completely:

square_pairs([Head | Tail], [[Head, SqHead] | SqTail]) :-
    SqHead is Head * Head,
    square_pairs(Tail, SqTail).
square_pairs([], []).

There's a handy predicate in Prolog called maplist which can be used for defining a relationship which runs parallel between two lists, which is the scenario we have here. We can bring back the square_pair/2 predicate and use maplist:

square_pairs(Numbers, SquarePairs) :-
    maplist(square_pair, Numbers, SquarePairs).

Prolog create list of lists

2 Answers