Prolog List Operations

Question

My problem is:

Write a PROLOG program that, given two lists of integers INDEXS and VALUES, returns a list whose first element is the value stored in the position corresponding to the first element of INDEXS of the list VALUES. For example, given INDXS=[2,1,4,3] and VALUES=[2,4,6,8], the output is [4,2,8,6].

So far I have done the following:

newlist([], [], void).
newlist([void|Tail], Values, X) :- newlist(Tail, Values, X).

newlist([H|T], Values, X) :- 
   nth1(H, Values, Curr), %%Get element nr H in Values and bind it to Curr
   add(Curr, X, [Curr|X]), %%Add Current to array X
   newlist(T, Values, X). %%Recursive send back Tail, the values and new array X

And query the following:

newlist([2,1], [2,3], X).

If my prolog code is ok, I want to show my new list in the variable X. How can I do this? (I have already tried to print it.

Answer 1

For fun, you can also use maplist.

Define nth_value to move the nth1 arguments to a convenient order:

nth_value(Values, Index, Item) :- nth1(Index, Values, Item).

Then:

newlist(INDXS, VALUES, R) :- maplist(nth_value(VALUES), INDXS, R).

Answer 2

You are close to a solution. The simplest case is when the list of indexes is empty. In this case, the list of values is of no consequence and the result is an empty list:

values([], _, []).

The _ is an anonymous variable. It can be regarded as a "don't care variable". If the list of indexes is not empty, we need to walk down the list and, for each index, retrieve the corresponding value at that position:

values([Index| Indexes], Values, [SelectedValue| SelectedValues]) :-
    nth1(Index, Values, SelectedValue),
    values(Indexes, Values, SelectedValues).

The nth1/3 predicate is a common library predicate that you can find implemented in several Prolog systems. If it is not available in the Prolog system you are using, defining it is a good exercise to learn Prolog.

Using your example as a sample query:

?- values([2,1,4,3], [2,4,6,8], SelectedValues).
SelectedValues = [4, 2, 8, 6].

Answer 3

There's a standard trick achieving this by pairing up the indices and the values and just sorting the resulting list, since pairs are sorted in lexicographical order. The indices will get sorted, and the values will get dragged along with them and find themselves in the correct places:

pair_up( X, Y, X-Y).
second( _-Y, Y).

newlist( Idxs, Vals, R) :- 
     maplist( pair_up, Idxs, Vals, L), 
     sort( L, S), 
     maplist( second, S, R).

It is independent of the indexing scheme: both 0- and 1-based indexing will work.

Another advantage is that it is linearithmic (due to the sorting), unlike the repeated nth solutions which are quadratic.

This assumes though that you are only rearranging the sequence, i.e. that both argument lists Idxs and Vals are of the same length.