Prolog List Question

Question

I'm trying to understand lists in prolog when I stumbpled over this problem:

there's a predicate mergeandmap/2 that should basically do this:

mergeandmap([[a1,...,an],...,[z1,...,zm]],[x1...xn])
            %----------list 1------------ -list 2--

List 2 consits of letters (for example [a,b,c]). List 1 consits of several lists with size(list2) elements containing 1s and 0s (for example: [[0,0,1],[1,0,1],[0,1,1]])

The prolog program should determine from list 1 which elements from list 2 should be printed and when.

For the above example:

([[0,0,1],[1,0,1],[0,1,1]],[a,b,c])  Result:  b c abc

Another example:

([[0,1,1],[1,0,1],[1,1,1]],[a,b,c])  Result:  bc ac abc
([[0,1],[1,0]],[a,b])  Result:  b a
([[0,1,1,1],[1,0,1,0],[1,1,1,0],[1,1,1,0]],[a,b,c,d])  Result:  bcd acd abcd a

I came up with this idea:

([[A,B,C],[D,E,F],[G,H,I]],[a,b,c])

1. "Merge" Lists into new list: by putting all the first subelements together, all the second subelements, all third, etc, etc... -> [ADG,BEH,CFI]

2. "Map" second list on Result from (1):

   [ADG,BEH,CFI] + [abc,abc,abc]

-> Value of uppercase letter decides wether lower case letter gets in the result.

Does anybody know how to implement this in prolog? Any help would really be appreciated!

Answer 1

As each of the lists is guaranteed to have the same length, you can easily subdivide the problem (similar to 'divide-and-conquer'). You first recursively walk through your list of 0/1-lists and for each of them create the corresponding output (again recursively).

mergeandmap([], _).
mergeandmap([X|Xs], Y) :- helper(X, Y), mergeandmap(Xs, Y).

And in a similar way you can then write the helper predicate with 3 lines: base case (empty list), 0 element, and 1 element. As X and Y are both of the same length, each recursive predicate then takes away the head element of a list. I think that should give a general idea of how to achieve that result.

By the way, you first example above seems wrong. The result should be c ac bc.

Answer 2

Well this is a an implementation of what you say, done in prolog exactly to your specifications. Your "Merge" is actually a function called transpose (in the context of matrices), and this happens to be in one of the SWI-Prolog libraries!

1 ?- [user].
|: mergeandmap(Bss,Ls) :- transpose(Bss,BssT), write('Result: '), maptostrings(BssT,Ls), write('\n').
|: maptostrings([],_).
|: maptostrings([Bs|Bss],Ls) :- write(' '), zipstringbits(Bs,Ls), maptostrings(Bss,Ls).
|: zipstringbits([],_).
|: zipstringbits([0|Bs],[_|Ls]) :- zipstringbits(Bs,Ls).
|: zipstringbits([1|Bs],[L|Ls]) :- write(L), zipstringbits(Bs,Ls).
|: :- use_module(library(clpfd)).
%    library(error) compiled into error 0.01 sec, 10,056 bytes
%   library(apply) compiled into apply 0.02 sec, 16,256 bytes
%   library(lists) compiled into lists 0.00 sec, 13,404 bytes
%   library(pairs) compiled into pairs 0.01 sec, 4,772 bytes
%  library(clpfd) compiled into clpfd 0.32 sec, 367,328 bytes
|: 
% user://1 compiled 0.44 sec, 369,348 bytes
true.

2 ?- mergeandmap([[0,0,1],[1,0,1],[0,1,1]],[a,b,c]).
Result:  b c abc
true .

3 ?- mergeandmap([[0,1,1],[1,0,1],[1,1,1]],[a,b,c]).
Result:  bc ac abc
true .

4 ?- mergeandmap([[0,1],[1,0]],[a,b]).
Result:  b a
true .

5 ?- mergeandmap([[0,1,1,1],[1,0,1,0],[1,1,1,0],[1,1,1,0]],[a,b,c,d]).
Result:  bcd acd abcd a
true .

6 ?- mergeandmap([[0,1],[1,0],[1,0]],[a,b,c]).
Result:  bc a
true .

7 ?- transpose([[A,B,C],[D,E,F],[G,H,I]],X).
X = [[A, D, G], [B, E, H], [C, F, I]].

Writing your own transpose function is a little more involved, as I decided to have a stab at it myself. After a while I did manage to get to a very neat solution, which by design, is able to accept lists of lists even when they're not rectangular! (Though it's still not as flexible as would be desired for use in mergeandmap unfortunately). Here's the code:

1 ?- [user].
|: transpose(Rs,Cs) :- emptylists(Rs),emptylists(Cs).
|: transpose([[X|R]|Rs],[[X|C]|Cs]) :- headsandtails(Rs,C,NRs), headsandtails(Cs,R,NCs), transpose(NRs,NCs).
|: headsandtails(Xss,[],[]) :- emptylists(Xss).
|: headsandtails([[X|Xs]|Xss],[X|Hs],[Xs|Ts]) :- headsandtails(Xss,Hs,Ts).
|: emptylists([]) :- !.
|: emptylists([[]|L]) :- emptylists(L).
|: 
% user://1 compiled 0.07 sec, 1,208 bytes
true.

2 ?- transpose([[1,2,3,4],[5,6,7],[8,9],[10]],Result).
Result = [[1, 5, 8, 10], [2, 6, 9], [3, 7], [4]] ;
false.

3 ?- transpose([[1,2,3,4],[5,6,7],[8,9,10,11],[10]],Result).
false.

4 ?- transpose([[1,2,3,4,5,7,8,3],[5,6,7],[8,9,10,11],[10]],Result).
false.

5 ?- transpose([[1,2,3,4,5,7,8,3],[5,6,7],[8,9,99],[10]],Result).
Result = [[1, 5, 8, 10], [2, 6, 9], [3, 7, 99], [4], [5], [7], [8], [3]] ;
false.

Basically how this works, is it checks the top left elements of the transpose and original are the same, and checks that the top row of one matches the left column of the other, and vice versa, then checks everything else iteratively until there's nothing left to check.

The cut operator ! on the emptylists predicate stops the answers growing off to the right with more empty lists, and means that it can terminate on trying to transpose something which doesn't have one (where it just keeps adding them and always fails to find an answer).

In summary for an all in one solution this is all the code you need:

mergeandmap(Bss,Ls) :- transpose(Bss,BssT), write('Result: '), maptostrings(BssT,Ls), write('\n').
maptostrings([],_).
maptostrings([Bs|Bss],Ls) :- write(' '), zipstringbits(Bs,Ls), maptostrings(Bss,Ls).
zipstringbits([],_).
zipstringbits([0|Bs],[_|Ls]) :- zipstringbits(Bs,Ls).
zipstringbits([1|Bs],[L|Ls]) :- write(L), zipstringbits(Bs,Ls).
transpose(Rs,Cs) :- emptylists(Rs),emptylists(Cs).
transpose([[X|R]|Rs],[[X|C]|Cs]) :- headsandtails(Rs,C,NRs), headsandtails(Cs,R,NCs), transpose(NRs,NCs).
headsandtails(Xss,[],[]) :- emptylists(Xss).
headsandtails([[X|Xs]|Xss],[X|Hs],[Xs|Ts]) :- headsandtails(Xss,Hs,Ts).
emptylists([]) :- !.
emptylists([[]|L]) :- emptylists(L).