CODEWITHSUNDEEP
listprolog
tuulik
tuulik

Reputation: 75

Removing heads from lists in Prolog

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..

Upvotes: 2

Views: 1564

Answers (4)

lurker
lurker

Reputation: 58324

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).

Upvotes: 3

coredump
coredump

Reputation: 38967

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.

Upvotes: 3

user1812457
user1812457

Reputation:

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]]).

Upvotes: 1

repeat
repeat

Reputation: 18726

We use 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]].

Upvotes: 2

Related Questions