cats.py

from functools import partial

class Monoid:
    @classmethod
    def mempty(cls):
        raise NotImplementedError
        
    def mappend(self, other):
        raise NotImplementedError
        
class Functor:
    def map(self, f):
        raise NotImplementedError
        
class Foldable:
    def foldl(self, f, default):
        raise NotImplementedError
        
    def foldr(self, f, default):
        raise NotImplementedError
        
class Applicative(Functor):
    @classmethod
    def pure(cls):
        raise NotImplementedError
        
    def apply(self, other):
        return self.liftA2(other, lambda f, x: f(x))
    
    def liftA2(self, other, f):
        return other.map(partial(partial, f)).apply(self)

list.py

from itertools import chain
from .tree import Tree
from .cats import Monoid, Foldable, Applicative

class List(Monoid, Foldable, Applicative):
    class Empty: pass

    def __init__(self, *args):
        self.val = Tree(self.Empty)
        if not args:
            return
        for x in reversed(args):
            self.val = Tree(Tree(x), self.val)
        
    def __iter__(self):
        for x in iter(self.val):
            if x != self.Empty:
                yield x
            
    def __str__(self):
        return str(list(iter(self)))
    
    def __repr__(self):
        return str(self)
    
    def __getitem__(self, n):
        if n >= 0:
            it = self
        else:
            it = self.foldl(List.cons, List.mempty())
            n = 1 - n
        for (i, x) in enumerate(it):
            if i == n:
                return x
        raise IndexError
        
    def __eq__(self, other):
        return self.val == other.val
    
    def cons(self, x):
        return List(x, *list(iter(self)))
    
    @classmethod
    def mempty(cls):
        return List()
    
    def mappend(self, other):
        return List(*list(chain(iter(self), iter(other))))
    
    def map(self, f):
        return self.foldr(lambda r, x: r.cons(f(x)), self.mempty())
    
    def foldl(self, f, default):
        r = default
        for x in iter(self):
            r = f(r, x)
        return r
    
    def foldr(self, f, default):
        r = default
        for x in reversed(list(iter(self))):
            r = f(r, x)
        return r
    
    @classmethod
    def pure(cls, x):
        return List(x)
    
    def liftA2(self, other, f):
        return List(*[f(s, o)
                      for s in iter(self)
                      for o in iter(other)])
        

tests.py

from operator import mul, add
from .list import List

a = List(1, 2, 3)                         # => [1, 2, 3]
b = a.map(partial(mul, 3))                # => [3, 6, 9]
c = a.liftA2(b, add)                      # => [4, 7, 10, 5, 8, 11, 6, 9, 12]
d = a.map(partial(partial, add)).apply(b) # => [4, 7, 10, 5, 8, 11, 6, 9, 12]
c == d                                    # True

tree.py

from collections import deque

class Tree:
    class Leaf: 
        def __init__(self, x):
            self.val = x

        def __eq__(self, other):
            return self.val == other.val

    class Branch:
        def __init__(self, left, right):
            self.left = left
            self.right = right
        
        def __eq__(self, other):
            return self.left == other.left and self.right == other.right
            
    def __init__(self, *args):
        n = len(args)
        assert 0 < n < 3
        self.val = (self.Leaf if n == 1 else self.Branch)(*args)
     
    def __iter__(self):
        stack = deque()
        stack.append(self)
        while stack:
            x = stack.pop()
            if isinstance(x.val, self.Leaf):
                yield x.val.val
            else:
                stack.append(x.val.right)
                stack.append(x.val.left)
                
    def __eq__(self, other):
        return self.val == other.val