Monadic Python (requires Python interpreter that supports deep-copying generators, like pypy)

Change.py

############## This is deprecated.
### NOTICE ### Use the NEW VERSION on GitHub:
############## https://github.com/JadenGeller/Guac

# Similiar to this Hasekell program: https://gist.github.com/JadenGeller/faef08a0278d41c0dcc682bca36a9ef8#file-solution-hs
@monadic(ListMonad)
def make_change(amount_still_owed, possible_coins):
    change = []
    while amount_still_owed > 0 and possible_coins:
        give_min_coin = yield [True, False] # nondeterministic choice, aka try both
        if give_min_coin:
            min_coin = possible_coins[0]
            change.append(min_coin)
            amount_still_owed -= min_coin
        else:
            del possible_coins[0]
    yield guard(amount_still_owed == 0)
    yield Lift(change)
    
print(make_change(18, [1, 5, 10, 25, 50, 100])) # -> [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 1, 1, 1, 10], [1, 1, 1, 5, 5, 5], [1, 1, 1, 5, 10]]

Examples.py

############## This is deprecated.
### NOTICE ### Use the NEW VERSION on GitHub:
############## https://github.com/JadenGeller/Guac

@monadic(ListMonad)
def test_list():
    x = yield [1, 2, 3]
    c = yield [1, 2, 3]
    yield guard(x != c)
    yield Lift(x + c)

@monadic(NoneMonad)
def test_none():
    x = yield 5
    c = yield None
    yield Lift(x * c)

@monadic(FunctionMonad)
def test_function():
    a = yield lambda x: x * 2
    b = yield lambda y: y + 10
    yield Lift(a + b)

@monadic(StateMonad)
def test_state():
    pop = lambda state: (state[0], state[1:])
    push = lambda x: lambda state: ((), [x] + state)
    a = yield pop
    if a == 5:
        yield push(5)
    else:
        yield push(7)
        yield push(8)
        yield push(9)

@monadic(ExceptionMonad)
def test_exception():
    x = yield 3
    y = yield RuntimeError('oh no!')
    yield Lift(x + y)
    
print(test_list())
print(test_none())
print(test_function()(3))
print(test_state()([2, 2, 2]))
print(test_exception())

Monad.py

############## This is deprecated.
### NOTICE ### Use the NEW VERSION on GitHub:
############## https://github.com/JadenGeller/Guac

# Requires pypy!
import copy
import abc
     
class MonadicOperation(metaclass=abc.ABCMeta):
    pass
    
class Lift(MonadicOperation):
    def __init__(self, value):
        self.value = value
        
    def apply(self, monad):
        return monad.lift(self.value)
        
    def __str__(self):
        return 'Lift({})'.format(self.value)
        
class Empty(MonadicOperation):
    def __init__(self):
        pass
    
    def apply(self, monad):
        return monad.empty()
        
    def __str__(self):
        return 'Empty'
      
class RunInDeferredContext(MonadicOperation):
    def __init__(self, computation):
        self.computation = computation
    
    def apply(self, monad):
        return monad.run(self.computation)
        
    def __str__(self):
        return 'RunInDeferredContext({})'.format(self.computation)
    
class Monad(metaclass=abc.ABCMeta):
    @staticmethod    
    @abc.abstractmethod
    def lift(x):
        return NotImplemented
        
    @staticmethod
    @abc.abstractmethod
    def bind(m, f):
        return NotImplemented
    
    @classmethod    
    def run(self, computation):
        def eval(monadic):
            if isinstance(monadic, MonadicOperation):
                return monadic.apply(self)
            else: # assume already monadic
                return monadic
                
        def step(monadic, continuation):
            monadic = eval(monadic)
            def proceed(x):
                # Requires Pypy!
                invocation = copy.deepcopy(continuation)
                try:
                    return step(invocation.send(x), invocation)
                except StopIteration:
                    return self.lift(x)
            return self.bind(monadic, proceed)
        return step(next(computation), computation)

def monadic(monad):
    def decorator(func):
        def wrapper(*args, **kwargs):
            if monad is Monad: # inherits calling context
                return RunInDeferredContext(func(*args, **kwargs))
            else:
                return monad.run(func(*args, **kwargs))
        return wrapper
    return decorator
   
class ListMonad(Monad):
    @staticmethod
    def lift(x):
        return [x]
    
    @staticmethod
    def bind(m, f):
        result = []
        for elem in m:
            result += f(elem)
        return result
        
    @staticmethod
    def empty():
        return []
    
class NoneMonad(Monad):
    @staticmethod
    def lift(x):
        return x
    
    @staticmethod
    def bind(m, f):
        if m is not None:
            return f(m)
        else:
            return None
            
    @staticmethod
    def empty():
        return None
    
class FunctionMonad(Monad):
    @staticmethod
    def lift(x):
        return lambda _: x
        
    @staticmethod
    def bind(m, f):
        return lambda x: f(m(x))(x)
        
class StateMonad(Monad):
    @staticmethod
    def lift(x):
        return lambda state: (x, state)
    
    @staticmethod
    def bind(m, f):
        def thread_state(state):
            (x, new_state) = m(state)
            return f(x)(new_state)
        return thread_state
    
class ExceptionMonad(Monad):
    @staticmethod
    def lift(x):
        return x
    
    @staticmethod
    def bind(m, f):
        if isinstance(m, Exception):
            return m
        else:
            return f(m)
   
@monadic(Monad)
def guard(cond):
    if cond:
        yield Lift(())
    else:
        yield Empty()

@monadic(Monad)
def fmap(f, m):
    yield Lift(f((yield m)))