wiki:Functions/Partition

partition

naive O(n2)

partition p xs = (filter p xs, filter (not . p) xs)

O(n)

partition p xs = foldr (select p) ([],[]) xs

where

select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

O(2n)

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

partition(Pred, [H | T], As, Bs) ->
    case Pred(H) of
        true -> partition(Pred, T, [H | As], Bs);
        false -> partition(Pred, T, As, [H | Bs])
    end;
partition(Pred, [], As, Bs) when is_function(Pred, 1) ->
    {reverse(As), reverse(Bs)}.
Last modified 4 years ago Last modified on Feb 27, 2017, 10:50:58 AM
Note: See TracWiki for help on using the wiki.