Giving same answer over and over, than listener crashes - Prolog

1
votes

Warning, I'm quite new to Prolog.

I've written a split predicate in Prolog. It splits a list into two new lists. One that contains items greater than Key, and one that contains items less than or equal to Key. It should only ever return one set of answers. The problem is if I type ; to check for more answers, it keeps giving me the answer I already got and then eventually the listener crashes. I was wondering if you could help me fix this?

Code:

split([],_,[],[]).
split([H|T],Key,Small,Big):-
    H=<Key,
    removeFirst(Small,H,NewSmall),
    split(T,Key,NewSmall,Big).
split([H|T],Key,Small,Big):-
    H>Key,
    removeFirst(Big,H,NewBig),
    split(T,Key,Small,NewBig).

removeFirst([H|T],H,T).
removeFirst(L,Key,Result):-
    divide(L,Key,F,E),
    X = F,
    Y = E,
    append(X,Y,Z),
    Result = Z.

Output:

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

S = [1, 2, 3]
B = [4, 5] ;

S = [1, 2, 3]
B = [4, 5] ;

S = [1, 2, 3]
B = [4, 5] ;
Listener crashes on 4th attempt.

1
prolog

1 Answers

2
votes

I suggest you resolve this algorithm in another way:

  • Define a recursive predicate (split/4) as you did, checking for each item in the input list, but build the resulting lists on return of recursion (that is, add the current item as the head of the appropriate list on the head of the clause).

It would be something like this:

split([], _, [], []).  % Base case
split([Item|Tail], Key, [Item|Small], Big):-
  Item =< Key,
  split(Tail, Key, Small, Big).
split([Item|Tail], Key, Small, [Item|Big]):-
  Item > Key,
  split(Tail, Key, Small, Big).