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

From itertools examples:

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

Answer 2

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 3

trues = [x for x in seq if pred(x)]
falses = [x for x in seq if not pred(x)]

That's the height of functional-programming style, unless you want more function calls.

Answer 4

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.