Bad Monads

bad_monads.py

from functools import wraps

def do(lift_func=iter):
    """
    Decorator that allows python generators to behave a bit like Haskell's do blocks.
    
    The basic intuition to follow is that the Haskell "x <- y" syntax is mimicked in python by "x = yield y",
    if it occurs inside a generator function decorated by @do().
    
    By passing different arguments to @do(), you can change which monad type is mimicked.
    By default, the behavior will mimic that of Haskell's List monad.
    Additional values for approximating the Maybe and State monads are provided below.
    
    Serious caveats apply.
    
    First, the decorated generator function is assumed to be deterministic, and to have no side effects
    on the environment outside of the generator. If this is not the case, the behavior may be subtly incorrect
    without good error messages.
    
    Second, the decorated generator function will be called and run potentially many times,
    for each single call to the wrapper returned by this decorator. This means that reasoning about
    the computational performance of this decorator will be unintuitive.
    """
    
    def _do(gen_func):
        @wraps(gen_func)
        def inner(*args, **kwds):
            frontier = [[None]]
            while frontier:
                path = frontier.pop()
                
                if path[-1] is None:
                    p = path
                else:
                    try:
                        p = path[:-1] + [next(path[-1])]
                    except StopIteration:
                        continue
                    else:
                        frontier.append(path)

                gen = gen_func(*args, **kwds)
            
                for inp in p[:-1]:
                    gen.send(inp)

                try:
                    branches = gen.send(p[-1])
                except StopIteration as e:
                    yield e.value
                else:
                    frontier.append(p + [lift_func(branches)])

        return inner
    return _do


# Lift func for Maybe
def Maybe(value):
    if value is not None:
        yield value

# Lift func for State
def State(start_value=None):
    state_box = [start_value]
    def _lift(op):
        yield op(state_box)
    return _lift

def StateGet():
    def _get(state_box):
        return state_box[0]
    return _get

def StatePut(value):
    def _put(state_box):
        state_box[0] = value
    return _put

if __name__ == '__main__':
    # examples
    from itertools import count

    #helper
    def take(it, n=None):
        """
        Consume n elements of the iterator it, returning them as a list.
        """
        if n is None:
            return list(it)

        result = []
        for i, x in enumerate(it):
            if i == n:
                break
            result.append(x)
        return result

    @do(Maybe)
    def print_value_if_present(dct, k):
        value = yield dct.get(k)
        print('value is', value)


    list(print_value_if_present({'a': 'horse'}, 'a')) # prints "value is horse"
    list(print_value_if_present({}, 'a')) # will not print anything

    @do(State())
    def idk():
        """
        Intended as a basic demonstration that the state operators work as expected.
        """
        yield StatePut(5)
        x = yield StateGet()
        yield StatePut(x + 1)
        y = yield StateGet()
        return x + y

    print(list(idk()))  # [11]

    
    #  List monad demos.
    
    @do()
    def monadic_range(x):
        """
        same behavior as single-arg range(), just here to demonstrate what yielding
        a range of values looks like
        """
        x = (yield range(x))
        return x

    print(list(monadic_range(5))) # [0, 1, 2, 3, 4]

    @do()
    def cartesian_product(*things):
        """
        yield the cartesian product of all the input args
        cartesian_product([1,2], [3,4]) -> (1, 3), (1, 4), (2, 3), (2, 4)
        """
        all_things = []
        for thing_range in things:
            all_things.append((yield thing_range))
        return tuple(all_things)

    print(take(cartesian_product([1,2], [3,4]))) # [(1,3), (1,4), (2,3), (2,4)]

    # the cartesian_product() above is a generalized/variadic version of foo1:
    # you can get combinatoric sequences by yielding a series of iterables
    @do()
    def cartesian_product_2(a, b):
        i = yield a
        j = yield b
        return (i, j)

    print(take(cartesian_product_2([1,2], [3,4]))) # [(1,3), (1,4), (2,3), (2,4)]

    # foo2 and foo3 show that infinite iterators work properly.
    # depending on the order in which the iterators are yielded,
    # the results will be different
    @do()
    def foo2():
        i = yield [1,2]
        j = yield count()
        return (i, j)

    # foo2 will never reach the second value for i, because the range of j is infinite
    print(take(foo2(), 5)) # [(1, 0), (1, 1), (1, 2), (1,3), (1,4)]

    @do()
    def foo3():
        i = yield count()
        j = yield [1,2]
        return (i, j)

    # foo3 yields the same things in reversed order from foo2, and so has different behavior
    print(take(foo3(), 5)) # [(0, 1), (0,2), (1, 1), (1, 2), (2, 1)]

    # foo4 demonstrates a pretty cool effect where yielding an empty iterable
    # will effectively filter out a branch of execution. This just comes free
    # as a natural consequence of the implementation!

    # This will only yield odd numbers
    @do()
    def odd_numbers():
        i = yield count()
        if i % 2 == 0:
            yield []
        return i

    print(take(odd_numbers(), 5)) # [1, 3, 5, 7, 9]

    #  Demonstrating how these can be naturally composed with each other
    @do()
    def doubled_odds():
        x = yield odd_numbers()
        return x * 2

    print(take(doubled_odds(), 5)) # [2, 6, 10, 14, 18]