Is there a functional programming idiom for filtering a list into trues and falses?

Question

Say you have some list L and you want to split it into two lists based on some boolean function P. That is, you want one list of all the elements l where P(l) is true and another list where P(l) is false.

I can implement this in Python like so:

def multifilter(pred,seq):
    trues,falses = [],[]
    for x in seq:
        if pred(x):
            trues.append(x)
        else:
            falses.append(x)
    return trues,falses

My question: Is there a functional programming idiom that accomplishes this?

Answer 1

Sure there is. In fact, there's one found in Python already. Look under itertools for the groupby function. However, you're going to have to sort the list by the function type first. I'm fairly certain that this is not what you're after but it's a start.

Me, I've always implemented what you're asking for via ifilter:

def multifilter( pred, arg ):
    return ifilter( pred, arg ), ifilter(lambda x: !pred(x), arg )

Answer 2

You can do this with a reduce that generates a 2-element tuple result.

reduce(lambda x,y: (x[0]+[y],x[1]) if somefunc(y) else (x[0],x[1]+y), somelist, ([],[]))

Returns a 2-tuple; first portion is a list of elements that make somefunc() return True, second is the rest.

Answer 3

Hoogle is a good tool for this. You can enter a function type and see all functions with that type. In this case we need as input: a list of a, and a function that takes an a and returns a boolean, and the output is a pair of lists of a. In Haskell syntax that's (a -> Bool) -> [a] -> ([a], [a]). From there we see the relevant function is partition. Implementation:

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

In Python:

partition = lambda p, xs: (filter(p, xs), filter(lambda f: not p(f), xs))

Or this is faster, but a bit uglier cause it's asymmetric:

partition = lambda p, xs: (filter(p, xs), [z for z in xs if not p(z)])

This does do twice the number of calculations you need, though, but I think you have to do that if you don't have mutation.

Answer 4

From itertools examples:

from itertools import tee, filterfalse
def partition(pred, iterable):
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)