lists:partition/2

[Raimo Niskanen]

Hello,

I am missing function in the module lists, one that using a predicate
partitions a list into two; one with all elements for which the
predicate was true, and one for the rest, while preserving the ordering
of the elements.

It could be defined as follows:

	partition(Pred, List) ->
	    partition(Pred, List, [], []).

	partition(Pred, [], ListTrue, ListFalse) ->
	    {reverse(ListTrue), reverse(ListFalse)};
	partition(Pred, [H | T], ListTrue, ListFalse) ->
	    case Pred(H) of
		true ->
		    partition(Pred, T, [H | ListTrue], ListFalse);
		false ->
		    partition(Pred, T, ListTrue, [H | ListFalse])
	    end.

This could be accomplished with lists:foldr/3 like this:

	partition(Pred, List) ->
	    foldr(
	        fun(Element, {ListTrue, ListFalse}) ->
	            case Pred(Element) of
	                true ->
	                    {[Element | ListTrue], ListFalse};
	                false ->
	                    {ListTrue, [Element | ListFalse]}
	            end
	        end,
	        {[], []},
	        List).
	        
The latter one is unfortunately not tail recursive, and it is less
efficient because it assembles / disassembles a tuple in each loop
recursion.

The questions are: is partition/2 sucha a useful function that it is
worthy of being included in the lists module, and are there any comments
on the implementation?

/ Raimo Niskanen, Ericsson UAB, Erlang/OTP.