Split list in prolog, produce two separate lists

1
votes

The Question:

Define a predicate split/4 which, when provided with a list L and integer N returns two lists, A and B, where A contains the items in L that are greater than or equal to N and B contains the items that are lower than N.

Sample query with expected result:

?- split([1, 5, 2, 3, 4], 3, A, B).
A = [5, 3, 4],
B = [1, 2].

My code: 

spit([], 0, [], []).
split([I|Is], N, [A|As], [_B|Bs]):-
    I >= N,
    A is I,
    split(Is, N, As, Bs).
split([I|Is], N, [_A|As], [B|Bs]):-
    I < N,
    B is I,
    split(Is, N, As, Bs).

Rather than producing A and B as required, my code simply returns false. I'm not sure why.

3
listprolog
Very similar to this question. – lurker

3 Answers

3
votes

Near to correct, but some small error.

Line by line:

a)

spit([], 0, [], []).

typo: spi vs split

The rule says "the split of an empty list by 0 are two empty lists", true, but too restrictive, change it to "the split of empty list is two empty list, no matter the number":

split([], _, [], []).

b)

split([I|Is], N, [A|As], [_B|Bs]):-
    I >= N,
    A is I,
    split(Is, N, As, Bs).

"B" remains undefined, even if you start it as _B to supress the warning. Change it to:

split([I|Is], N, [I|As], Bs ):-
    I >= N,
    split(Is, N, As, Bs).

c)

split([I|Is], N, [_A|As], [B|Bs]):-
    I < N,
    B is I,
    split(Is, N, As, Bs).

same as previous.

2
votes

As an alternative to partition/4, use tpartition/4 together with (#=<)/3, like this:

?- tpartition(#=<(3),[1,5,2,3,4],As,Bs).
As = [5,3,4], Bs = [1,2].

Thanks to and (#=<)/3, you can run queries that are a lot more general!

For details, look at my answer to the related question "Splitting a list of integers into a list of positive integers and a list of negative integers".

1
votes

I think it's homework, because, with SWI-Prolog, you have partition/4

partition(:Pred, +List, ?Included, ?Excluded) [det]

Filter elements of List according to Pred.
True if Included contains all elements for which call(Pred, X) succeeds and Excluded contains the remaining elements.

split(L, N, A, B) :-
    partition( =<(N), L, A, B).