pythonpredicatefunction-compositionpointfree

Pointfree function combination in Python


I have some predicates, e.g.:

is_divisible_by_13 = lambda i: i % 13 == 0
is_palindrome = lambda x: str(x) == str(x)[::-1]

and want to logically combine them as in:

filter(lambda x: is_divisible_by_13(x) and is_palindrome(x), range(1000,10000))

The question is now: Can such combination be written in a pointfree style, such as:

filter(is_divisible_by_13 and is_palindrome, range(1000,10000))

This has of course not the desired effect because the truth value of lambda functions is True and and and or are short-circuiting operators. The closest thing I came up with was to define a class P which is a simple predicate container that implements __call__() and has the methods and_() and or_() to combine predicates. The definition of P is as follows:

import copy

class P(object):
    def __init__(self, predicate):
        self.pred = predicate

    def __call__(self, obj):
        return self.pred(obj)

    def __copy_pred(self):
        return copy.copy(self.pred)

    def and_(self, predicate):
        pred = self.__copy_pred()
        self.pred = lambda x: pred(x) and predicate(x)
        return self

    def or_(self, predicate):
        pred = self.__copy_pred()
        self.pred = lambda x: pred(x) or predicate(x)
        return self

With P I can now create a new predicate that is a combination of predicates like this:

P(is_divisible_by_13).and_(is_palindrome)

which is equivalent to the above lambda function. This comes closer to what I'd like to have, but it is also not pointfree (the points are now the predicates itself instead of their arguments). Now the second question is: Is there a better or shorter way (maybe without parentheses and dots) to combine predicates in Python than using classes like P and without using (lambda) functions?


Solution

  • You can override the & (bitwise AND) operator in Python by adding an __and__ method to the P class. You could then write something like:

    P(is_divisible_by_13) & P(is_palindrome)
    

    or even

    P(is_divisible_by_13) & is_palindrome
    

    Similarly, you can override the | (bitwise OR) operator by adding an __or__ method and the ~ (bitwise negation) operator by adding a __not__ method. Note that you cannot override the built-in and, or and not operator, so this is probably as close to your goal as possible. You still need to have a P instance as the leftmost argument.

    For sake of completeness, you may also override the in-place variants (__iand__, __ior__) and the right-side variants (__rand__, __ror__) of these operators.

    Code example (untested, feel free to correct):

    class P(object):
        def __init__(self, predicate):
            self.pred = predicate
    
        def __call__(self, obj):
            return self.pred(obj)
    
        def __copy_pred(self):
            return copy.copy(self.pred)
    
        def __and__(self, predicate):
            def func(obj):
                return self.pred(obj) and predicate(obj)
            return P(func)
    
        def __or__(self, predicate):
            def func(obj):
                return self.pred(obj) or predicate(obj)
            return P(func)
    

    One more trick to bring you closer to point-free nirvana is the following decorator:

    from functools import update_wrapper
    
    def predicate(func):
        """Decorator that constructs a predicate (``P``) instance from
        the given function."""
        result = P(func)
        update_wrapper(result, func)
        return result
    

    You can then tag your predicates with the predicate decorator to make them an instance of P automatically:

    @predicate
    def is_divisible_by_13(number):
        return number % 13 == 0
    
    @predicate
    def is_palindrome(number):
        return str(number) == str(number)[::-1]
    
    >>> pred = (is_divisible_by_13 & is_palindrome)
    >>> print [x for x in xrange(1, 1000) if pred(x)]
    [494, 585, 676, 767, 858, 949]