Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Working with list of lists in Prolog

Please help me to solve this problem: I have a list of lists

[[1,2],[3,4]]

How do I get:

[1,3]

[1,4]

[2,3]

[2,4]

Or if I have a list of lists

[[1,2],[3,4],[6,7]]

How do I get:

[1,3,6]

[1,3,7]

[1,4,6]

[1,4,7]

[2,3,6]

[2,3,7]

[2,4,6]

[2,4,7]

like image 688
Welcome789 Avatar asked Jan 25 '12 00:01

Welcome789


People also ask

How do I make a list list in Prolog?

In Prolog list elements are enclosed by brackets and separated by commas. Another way to represent a list is to use the head/tail notation [H|T]. Here the head of the list, H, is separated from the tail of the list, T, by a vertical bar. The tail of a list is the original list with its first element removed.

How do you access list elements in Prolog?

Unlike arrays in other programming languages where we can directly access any element of the array, prolog lists allow direct access of the first element only which is denoted as Head. Therefore we can write a prolog list as : [Head | Rest], where Rest is the rest of the list excluding the first element Head.

What does \+ mean in Prolog?

Because of the problems of negation-as-failure, negation in Prolog is represented in modern Prolog interpreters using the symbol \+ , which is supposed to be a mnemonic for not provable with the \ standing for not and the + for provable.


2 Answers

The predicate for accessing a single list element is the most basic Prolog building block: member/2.

And you want a list of all lists' elements: maplist/3 does such mapping. Thus we can write

combine(Ls, Rs) :-
    maplist(get1, Ls, Rs).
get1(L, E) :-
    member(E, L).

note that get1/2 is only required so that we swap the member/2 arguments. But because in (pure) Prolog we are describing relations between arguments, we can swap arguments' order and simplify it even more:

combine(Ls, Rs) :-
    maplist(member, Rs, Ls).

Test output:

?- combine( [[1,2],[a,b]], Xs).
Xs = [1, a] ;
Xs = [1, b] ;
Xs = [2, a] ;
Xs = [2, b].

%% this is the same as:
       %% maplist( member, Xs, [[1,2],[a,b]]) :-
       %%          member( X1,  [1,2]      ),
       %%          member( X2,        [a,b]),  Xs = [X1,X2].

edit

A joke: really, my first combine/2 should have been written like

combine(Ls, Rs) :-
    maplist(rebmem, Ls, Rs).
rebmem(L, E) :-
    member(E, L).
like image 69
CapelliC Avatar answered Sep 28 '22 01:09

CapelliC


You can do something like this:

lists([], []).
lists([[Head|_]|Lists], [Head|L]):-
  lists(Lists, L).
lists([[_,Head|Tail]|Lists], L):-
  lists([[Head|Tail]|Lists], L).

That is, take the first element of the first list in your input list and continue recursively with the remaining lists. As a second chance, skip that element and redo with the remaining elements.

like image 36
gusbro Avatar answered Sep 28 '22 02:09

gusbro