Removing heads from lists in Prolog

Question

I'm trying to write a predicate to remove the head from every list in list of lists and add the tails to a new list. The resulting list should be returned as the second parameter.

Here's the attempt:

construct_new(S,New) :-
    New = [],
    new_situation(S,New).

new_situation([],_).
new_situation([H|T], New) :-
    chop(H, H1),
    new_situation(T, [H1|New]).

chop([_|T], T).

You would call it like this:

construct_new([[x,x],[b,c],[d,e,f]],S).

This, however, only produces output true..

Answer 1

Step-by-step execution

1. Your query is construct_new(Input,Output), for some instanciated Input list.
2. The first statement in construct_new/2 unifies Output (a.k.a. New) with the empty list. Where is the returned list supposed to be available for the caller? Both arguments are now unified.
3. You call new_situation(Input,[])
4. You match the second clause new_situation([H|T],[]), which performs its task recursively (step 4, ...), until ...
5. You reach new_situation([],_), which successfully discards the intermediate list you built.

Solutions

• Write a simple recursive predicate:

  new_situation([],[]).
  new_situation([[_|L]|T],[L|R]) :-
      new_situation(T,R).
  

• Use maplist:

  construct_new(S,R) :-
      maplist(chop,S,R).
  

Remark

As pointed out by other answers and comments, your predicates are badly named. construct_new is not a relation, but an action, and could be used to represent almost anything. I tend to like chop because it clearly conveys the act of beheading, but this is not an appropriate name for a relation. repeat's list_head_tail(L,H,T) is declarative and associates variables to their roles. When using maplist, the other predicate (new_situation) doesn't even need to exist...

_{...even though guillotine/3 is tempting.}

Answer 2

This could be done with a DCG:

owth(Lists, Tails) :-
    phrase(tails(Tails), Lists).

tails([]) --> [].
tails([T|Tails]) --> [[_|T]], tails(Tails).

Yielding these queries:

| ?- owth([[x,x],[b,c],[d,e,f]], T).

T = [[x],[c],[e,f]] ? ;

no
| ?- owth(L, [[x],[c],[e,f]]).

L = [[_,x],[_,c],[_,e,f]]

yes

(owth = Off with their heads! or, if used the other direction, On with their heads!)

If you also want to capture the heads, you can enhance it as follows:

owth(Lists, Heads, Tails) :-
    phrase(tails(Heads, Tails), Lists).

tails([], []) --> [].
tails([H|Hs], [T|Tails]) --> [[H|T]], tails(Hs, Tails).

Answer 3

We use meta-predicate maplist/[3-4] with one of these following auxiliary predicates:

list_tail([_|Xs],Xs).

list_head_tail([X|Xs],X,Xs).

Let's run some queries!

?- maplist(list_head_tail,[[x,x],[b,c],[d,e,f]],Heads,Tails).
Heads = [x,b,d],
Tails = [[x],[c],[e,f]].

If you are only interested in the tails, use maplist/4 together with list_head_tail/3 ...

?- maplist(list_head_tail,[[x,x],[b,c],[d,e,f]],_,Tails).
Tails = [[x],[c],[e,f]].

... or, even simpler, maplist/3 in tandem with list_tail/2:

?- maplist(list_tail,[[x,x],[b,c],[d,e,f]],Tails).
Tails = [[x],[c],[e,f]].

Answer 4

You can also use the somewhat ugly one-liner with findall/3:

?- L = [[x,x],[b,c],[d,e,f]],
   findall(T, ( member(M, L), append([_], T, M) ), R).
R = [[x], [c], [e, f]].

(OK, technically a two-liner. Either way, you don't even need to define a helper predicate.)

But definitely prefer the maplist solution that uses chop as shown above.

If you do the maplist expansion by hand, and name your chop/2 a bit better, you would get:

lists_tails([], []).
lists_tails([X|Xs], [T|Ts]) :-
    list_tail(X, T),
    lists_tails(Xs, Ts).

And since you can do unification in the head of the predicate, you can transform this to:

lists_tails([], []).
lists_tails([[_|T]|Xs], [T|Ts]) :-
    lists_tails(Xs, Ts).

But this is identical to what you have in the other answer.

Exercise: why can't we say:

?- maplist(append([_]), R, [[x,x],[b,c],[d,e,f]]).