Prolog: Take the first "N" elements of a list

Question

I need to write a Prolog predicate take(L, N, L1) which succeeds if list L1 contains the first N elements of list L, in the same order. For example:

?- take([5,1,2,7], 3, L1).
L1 = [5,1,2]
?- take([5,1,2,7], 10, L1).
L1 = [5,1,2,7]

Prolog thus far is making little sense to me, and I'm having a hard time breaking it down. Here is what I have so far:

take([H|T], 0, []).
take([H|T], N, L1) :-
   take(T, X, L2),
   X is N-1.

Can you please explain what I did wrong here?

Just a sidenote, it's a best practice to put recursive calls at the end of a recursive rule. In this original example, where would X reach 0? I haven't tested this particular program but I would surmise that at some point the list would simply run out of elements and return false, which would then start stepping back and triggering X is N-1. The reverse case though, adding an element to a list, let's say a random integer? You set X to 10 because you want 10 elements. X is then never decremented and the program loops until it runs out of memory. — G_V, Jan 19 '18 at 09:11

false · Answer 1 · 2021-03-08T10:32:54.903

8

Here is a definition that implements the relational counterpart to take in functional languages like Haskell¹. First, the argument order should be different which facilitates partial application. There is a cut, but only after the error checking built-in (=<)/2 which produces an instantiation_error should the argument contain a variable.

take(N, _, Xs) :- N =< 0, !, N =:= 0, Xs = [].
take(_, [], []).
take(N, [X|Xs], [X|Ys]) :- M is N-1, take(M, Xs, Ys).

?- take(2, Xs, Ys).
   Xs = [], Ys = []
;  Xs = [_A], Ys = [_A]
;  Xs = [_A,_B|_C], Ys = [_A,_B].

Note how above query reads:

How can one take 2 elements from Xs to get Ys?

And there are 3 different answers. If Xs is empty, then so is Ys. If Xs is a list with one element, then so is Ys. If Xs has at least 2 elements, then those two are Ys.

^{1) The only difference being that take(-1, Xs,Ys) fails (for all Xs, Ys). Probably the best would be to issue a domain_error similar to arg(-1,s(1),2)}

edited Mar 08 '21 at 10:32

answered Nov 27 '14 at 00:26

false

10,264
13
101
209

Could you avoid the cut by having the three cases be non-overlapping: 1) N=0, so 'yield' an empty list, 2) N>0 and an empty list, so 'yield' an empty list, and 3) N>0 and a non-empty list, so recurse? – Scott Hunter Nov 27 '14 at 10:18
3

@ScottHunter: Yes, indeed, but this would then be a waste. I'd do it when using `#>` instead. – false Nov 27 '14 at 13:01
Do the answers of `?- take(2.5, Xs, Ys).` make sense to you? I find them somewhat puzzling... – repeat Jul 05 '16 at 16:00
@false. OK, makes sense to me now. Thx! – repeat Jul 05 '16 at 18:33

score 3 · Answer 2 · answered Nov 29 '14 at 18:37

3

findall/3 it's a bit the 'swiss knife' of Prolog. I would use this snippet:

take(Src,N,L) :- findall(E, (nth1(I,Src,E), I =< N), L).

answered Nov 29 '14 at 18:37

CapelliC

59,646
5
47
90

repeat · Answer 3 · 2021-03-11T08:57:33.140

3

The code by @CapelliC works if the instantiation is right; if not, it can show erratic behavior:

?- take(Es, 0, Xs).
**LOOPS**                   % trouble: goal does not terminate

?- take([A,_], 1, [x]).          
true.                       % trouble: variable A remains unbound

To safeguard against this you can use iwhen/2 like so:

take(Src, N, L) :-
   iwhen(ground(N+Src), findall(E, (nth1(I,Src,E), I =< N), L)).

Sample queries run with SWI-Prolog 8.0.0:

?- take([a,b,c,d,e,f], 3, Ls).
Ls = [a,b,c].

?- take([a,b,c,d,e,f], N, Ls).
ERROR: Arguments are not sufficiently instantiated

?- take(Es, 0, Xs).
ERROR: Arguments are not sufficiently instantiated

?- take([A,_], 1, [x]).
ERROR: Arguments are not sufficiently instantiated

Safer now!

edited Mar 11 '21 at 08:57

answered Jul 05 '16 at 19:04

repeat

18,496
4
54
166

2

It seems a good style to follow the syntax of `when(Cond, Goal_)` for tests of instantiation that is `( ground(Es) -> take_unsafe(Es, N, Xs) ; throw(error(instantiation_error,_),_) )`. – false Jul 06 '16 at 17:05
@false. What about processors that do not offer `when/2`? – repeat Jul 06 '16 at 17:48
2

My comment was only about the **form**. That is, instead of extra clauses with cut, rather use the form above. No more than that. – false Jul 06 '16 at 23:02
1

BTW, what do you mean by "above"? – false Mar 08 '21 at 09:31
@false. Good one. Fixed. – repeat Mar 11 '21 at 08:57

score 1 · Answer 4 · 2014-11-26T15:31:07.350

1

The obvious solution would be:

take(List, N, Prefix) :-
    length(List, Len),
    (   Len =< N
    ->  Prefix = List
    ;   length(Prefix, N),
        append(Prefix, _, List)
    ).

Less thinking means less opportunity for mistakes. It also makes the predicate more general.

edited Nov 26 '14 at 15:31

answered Nov 26 '14 at 15:25

4

HET! This implies that `List` has `N` elements. But it should also succeed for `List = []` – false Nov 26 '14 at 15:27
@false Yes, now I saw the examples. – Nov 26 '14 at 15:29
5

You current solution implies that the `List` is a list, thus of finite length, but only a prefix is needed, if at all. – false Nov 26 '14 at 15:33

Rasika Weragoda · Answer 5 · 2019-11-21T12:45:00.887

1

your base case is fine

take([H|T], 0, []).

And also you can say what if N is 1

take([H|T],1,[H]).

But you recursive case some variable is not defined like L2. So we can write this as

take([X|T1],N,[X|T2]):-
N>=0,
N1 is N-1,
take(T1,N1,T2).

which case all varibles are pattern-matched.

edited Nov 21 '19 at 12:45

answered Nov 21 '19 at 12:35

Rasika Weragoda

936
14
15

You could also use `take([_|_], 0, []).` `take([H|_],1,[H]).` for the first two lines to have anonymous variables instead of getting singleton variable error. – Adomas202 Dec 12 '19 at 07:30

score 0 · Answer 6 · answered Oct 05 '20 at 06:33

0

take(L, N, L1) :- length(L1, N), append(L1, _, L).

answered Oct 05 '20 at 06:33

rajashekar

3,460
11
27

This infinite-loops at the end of e.g.: take([a, b], N, L). – brebs Feb 22 '22 at 14:46

brebs · Answer 7 · 2022-05-03T08:11:46.713

This is performant, general and deterministic:

first_elements_of_list(IntElems, LongLst, ShortLst) :-
    LongLst = [H|T],
    (   nonvar(IntElems) -> Once = true
    ;   is_list(ShortLst) -> Once = true
    ;   Once = false
    ),
    first_elements_of_list_(T, H, 1, IntElems, ShortLst),
    (Once = true -> ! ; true).

first_elements_of_list_([], H, I, I, [H]).

first_elements_of_list_([_|_], H, I, I, [H]).

first_elements_of_list_([H|LongLst], PrevH, Upto, IntElems, [PrevH|ShortLst]) :-
    Upto1 is Upto + 1,
    first_elements_of_list_(LongLst, H, Upto1, IntElems, ShortLst).

Result in swi-prolog:

?- first_elements_of_list(N, [a, b, c], S).
N = 1,
S = [a] ;
N = 2,
S = [a,b] ;
N = 3,
S = [a,b,c].

?- first_elements_of_list(2, [a, b, c], S).
S = [a,b].

Below is a variant which also supports:

?- first_elements_of_list_more(10, [5, 1, 2, 7], L1).
L1 = [5,1,2,7].

first_elements_of_list_more(IntElems, [H|LongLst], [H|ShortLst]) :-
    once_if_nonvar(IntElems, first_elements_of_list_more_(LongLst, 1, IntElems, ShortLst)).

first_elements_of_list_more_([], Inc, Elems, []) :-
    (var(Elems) -> Inc = Elems
    ; Elems >= Inc).

first_elements_of_list_more_([_|_], E, E, []).

first_elements_of_list_more_([H|LongLst], Upto, IntElems, [H|ShortLst]) :-
    succ(Upto, Upto1),
    first_elements_of_list_more_(LongLst, Upto1, IntElems, ShortLst).

once_if_nonvar(Var, Expr) :-
    nonvar(Var, Bool),
    call(Expr),
    (Bool == true -> ! ; true).

nonvar(Var, Bool) :-
    (nonvar(Var) -> Bool = true ; Bool = false).

OP's example fails: `first_elements_of_list(10,[5,1,2,7],L1)` — false, Mar 08 '22 at 15:22
Added variant to support: first_elements_of_list_more(10, [5, 1, 2, 7], L1). — brebs, Mar 08 '22 at 19:05

Prolog: Take the first "N" elements of a list

7 Answers7

Linked

Related