How do I map certain values to a list in Prolog?

Question

So, I have a predicate defined as map(Letter, Number). For instance:

map(j, 0).
map(k, 1).

etc.

I need to make a function called map_list(List, X) that creates a List X with the Number pairs from the map predicate. For example:

map_list([j, j, k, k], X).

X = [0, 0, 1, 1].

Here's what I have so far:

map_list([], []).
map_list([], _).
map_list([Head|Tail], Ans) :-
   map(Head, N),
   append(Ans, [N], NewAns),
   map_list(Tail, NewAns).

All it keeps doing is appending random "junk" to the new list, and never ends. Can anyone help? Thanks!

Answer 1

Your code:

map_list([], []).

This mean [] is mapped to [], or "the list of letters [] is in a (bidirectional) relation map_list with the list of integers []". Good!

map_list([], _).

This mean [] is mapped to anything, or "the list of letters [] is in a (bidirectional) relation map_list with anything in the computer's universe". BAD!

map_list([Head|Tail], Ans) :- map(Head, N),
                              append(Ans, [N], NewAns),
                              map_list(Tail, NewAns).

This means "the nonempty list of letters [Head|Tail] is in a (bidirectional) relation map_list with Ans defined as follows:

1. map(Head, N) with the usual meaning.
2. The predefined relation append exists between the two lists Ans, [N] and NewAns. At this point Ans is as yet unconstrained if you issued the query map_list([j,k],Ans), so, Prolog will only know that NewAns is a list starting with Ans (the only thing we know about it is that it must be a list) and ending in the member N. In fact, you are using append the wrong way round.
3. NewAns is recursively made more precise in the map_list(Tail, NewAns) but at this point, we are not even sure what we are computing.

In any case, you are getting an increasing long list of unconstrained variables (the "junk"):

?- map_list([j,k],X).
X = [] ;
X = [_7280] ;
X = [_7280, _7292] ;
X = [_7280, _7292, _7304] ;
X = [_7280, _7292, _7304, _7316] ;
X = [_7280, _7292, _7304, _7316, _7328] 

Let's fix this into by

1. Dropping the "anything" match map_list([], _).
2. Correctly using append to construct the result list.

Like this:

map(j, 0).
map(k, 1).
map_list([], []).
map_list([Head|Tail], Ans) :- map(Head, N),
                              append([N], TailAns, Ans),
                              map_list(Tail, TailAns).

This works.

?-  map_list([j,k],X).
X = [0, 1].

Note the information flow. Unlike in imperative languages, the information at append time is as yet incomplete. We know N if it was passed in the query, but we don't know anything TailAns yet, which has yet to be constructed. It is determined to a full extend by the recursive call only. (The compiler or Prolog virtual machine might optimize this into a loop modifying a structure on the heap instead of a the stack, depends).

You could write the following to perform "append on return from the recursive call", which is more like what's done in imperative languages:

map(j, 0).
map(k, 1).
map_list([], []).
map_list([Head|Tail], Ans) :- map(Head, N),
                              map_list(Tail, TailAns),
                              append([N], TailAns, Ans).

Addendum to respond to comment question

I love trying to explain Prolog. It is always confusing but brings new prespectives. (Or you could try the short-but-pricey The Reasoned Schemer, but you need to know about Scheme first).

Ok, so:

map_list([Head|Tail], Ans) :-
   map(Head, N),
   append([N], TailAns, Ans),
   map_list(Tail, TailAns).

A TailAns appears out of the blue in the body of the predicate (or procedure). This is a "fresh" variable (there is no need to declare it first in Prolog). At the state of the computation at which TailAns appears for the first time, nothing is know about it yet, it is unconstrained.

To better figure out what's happening, replace the word "variable" by the word "blackboard". We can then "create an empty/fresh blackboard", "refer to a blackboard by name", "pass the blackboard to another predicate (or procedure)", have a predicate "refine whatever is on the blackboard" by specifying additional details. The blackboard can also be "shared among calls", and be referenced by its name on several places in the same call, including through the contents of other blackboards:

A = g(B,1,C), B = h(a,k,C).

Is a statement about blackboards A, B, C, where we state that the contents of blackboard A is g(B,1,C) and the contents of blackboard B is h(a,k,C). This statement may or may not be correct at any point in time, depending on what other parts of the code have already stated about those blackboards. We say nothing about the contents of blackboard C.

Similarly, a call at the Prolog REPL (top level) to predicate append/3:

?- append([1,2],[3],C).

creates three blackboards,

• one unnamed with [1,2] as content
• one unnamed with [3] as content
• one named C with no/unspecified content ("a fresh variable")

The task of append/3 is now to refine the contents of these three blackboards so that the content of blackboard 3 contains a list that is the concatenation of the contents of blackboard 1 and 2.

append/3 implements not a function, but a relation (which is a generalization of the function), or at least it tries to approach that ideal. Unlike in a function where information flows necessarily from input argument to output result, information between the relation arguments flows more freely. For example, you could obtain the input arguments given the output. Such is the case here.

?- append(X,[1,2],[3]).
false.

Well, there is no solution for the above. But:

?- append(X,[1,2],[first,1,2]).
X = [first] ;
false.

Using the blackboard mental image, append/3 will refine blackboard X such that a concatenation of X and [1,2] gives [first,1,2] (the last two written on distinct blackboards unnamed at the toplevel). This is achieved by putting [first] on the blackboard whose name at the toplevel is X.

Same with determining the result given the lists to be concatenated:

?- append([first],[1,2],X).
X = [first, 1, 2].

Same with determining the second argument given the first and the result of the concatenation:

?- append([first],X,[first,1,2]).
X = [1, 2].

Unconstrained blackboards lead to guessing, with fresh blackboards pulled out of thin air named _somenumber appearing:

?- append(X,Y,Z).
X = [], Y = Z ;
X = [_5070], Z = [_5070|Y] ;
X = [_5070, _5082], Z = [_5070, _5082|Y] ;
etc.

The blackboard can of course refer to other blackboards via of variable names, potentially the same variable appears in many places:

?- append([1,X,X],[1,X,X],[1,2|R]).
X = 2,
R = [2, 1, 2, 2].

So cool!

The blackboard image helps to explain that information is given to predicate on call, and the predicate can return information back by modifying said blackboard.

Note that the content of a blackboard is ever made more precise by filling in unspecified variables. It is never made less precise by knocking out "know things" and replacing them with variables.

However, if we ask for impossible thinsg to appear on a blackboard, computation will fail and "backtrack" to a previous state for another attempt: the blackboards constructed are trashed and earlier blackboards are restored.

So back to the second line of

map_list([Head|Tail], Ans) :- map(Head, N),
                              append([N], TailAns, Ans),
                              map_list(Tail, TailAns).

append/3 will now try to determine whether the concatenation of list [N] and list TailAns gives list Ans.

It will either

• Say true and update the blackboards N, TailAnsand Ans, and computation can continue.
• Say false and computation "backtracks".

In the present case, append/3 will be able to say the content of blackboard Ans is exactly [N|TailAns], but nothing more.

Actually, at this point of the computation, there is some concrete value on the blackboard N, but TailAns is completely unknown, it just must be some kind of list (and that's not even checked, as Prolog has no types).

What TailAns stands for is only made more concrete by the subsequent recursive call map_list(Tail, TailAns). After the deepest recursive call, it will contain [], and thus Ans, constructed earlier, will become a bit more precise, in fact with TailAns now known to be [] it morphs from [N|TailAns] to [N|[]], written simply as [N] or, as N is know to be 1 at this point, [1]. This also means that the [N|TailAns] of the caller will be refined from its [N|TailAns] to [N|[1]], written simply as [N,1] or, as N is know in the context of the caller to be 0, [0,1].

Answer 2

I think you're over complicating it with the append calls.

It's this simple:

map_list([], []).
map_list([H1|T1],[H2|T2]) :-
    map(H1,H2),
    map_list(T1,T2).