prolog

How to split list in Prolog?


I want to write a predicate split(List, Pivot, Result) holds when Result is a list of sublists that List divided by Pivot. For example split(['_', '_', '#', '_', '#', '_'], '#', [['_','_'], ['_'], ['_']]) is true.

My code is like this and it doesn't work:

split(List, Pivot, Result) :-
split(List, Pivot, _, _, Result).

split(List, Pivot, Left, Right, X|Xs) :-
    append(Left, [Pivot|Right], List),
    !,
    member(Pivot, Right)
    ->  X = [Left],
        split(Right, Pivot, _, _, Xs)
    ;   X = [[Left]|[Right]].

I don't think my approach is clever either. Can someone give me some advice? Thank you.


Solution

  • Here is one way of doing it:

    split(L,P,R):-split(L,P,[],R).
    split([],_,[],[]).
    split([],_,S,[S]) :- S \= [].
    split([P|T],P,[],R) :- split(T,P,[],R).
    split([P|T],P,L,[L|R]) :- L \= [], split(T,P,[],R).
    split([H|T],P,S,R) :- H \= P, append(S, [H], S2), split(T,P,S2,R).
    

    Demo.

    split/4 predicate adds a parameter at position 3 which means "list constructed so far". split/3 is a simple redirection with the "list so far" set to [].

    Clauses on lines 2 and 4 handle situations when two Pivots are in a row, and when the pivot is detected at the end of the sequence. These clauses prevent insertion of empty lists.