Separate collection of lists by without losing the order?

Question

Is there some way in SWI Prolog to separate a list of lists e.g. of following form:

[[left, 1], [left, 2], [right, 3], [right, 4]]

into two lists separated by the first values, in the example:

[[left, 1], [left, 2]] and [[right, 3], [right, 4]]

Answer 1

How about:

separate_lists(Lst, SplitA, SplitB) :-
    Lst = [[K, V]|T],
    SplitA = [[K, V]|TailA],
    separate_lists_(T, K, TailA, SplitB).
    
separate_lists_([], _, [], []).
separate_lists_([[K, V]|T], K, SplitA, SplitB) :-
    !,
    % Same key - still looping through list A
    SplitA = [[K, V]|SplitA0],
    separate_lists_(T, K, SplitA0, SplitB).
% Put remainder in list B
separate_lists_([[K, V]|T], _PrevK, [], [[K, V]|T]).

Results in swi-prolog:

?- separate_lists([[left, 1], [left, 2], [right, 3], [right, 4]], A, B).
A = [[left,1],[left,2]],
B = [[right,3],[right,4]].

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