monad.py

from abc import abstractmethod
from itertools import chain, imap

from typing import Any, Iterable
from typing import Callable, Generic, List
from typing import TypeVar

A = TypeVar('A')
B = TypeVar('B')
C = TypeVar('C')


class Monoid(Generic[A]):
    @abstractmethod
    def mappend(self, a):
        # type: (A) -> Monoid[A]
        pass

    @classmethod
    @abstractmethod
    def mzero(cls):
        # type: () -> Monoid[A]
        pass

    @classmethod
    def mconcat(cls, l):
        # type: (List[A]) -> A
        return reduce(cls.mappend, l, initial=cls.mzero)


class Functor(Generic[A]):
    @abstractmethod
    def fmap(self, f):
        # type: (Callable[A, B]) -> Functor[B]
        pass


class Applicative(Functor[A]):
    @classmethod
    @abstractmethod
    def pure(cls, a):
        # type: (A) -> Applicative[A]
        pass

    @abstractmethod
    def apply(self, f_f):
        # type: (Applicative[Callable[A, B]]) -> Applicative[B]
        pass


class Monad(Applicative[A]):
    @abstractmethod
    def bind(self, f):
        # type: (Callable[A, Monad[B]]) -> Monad[B]
        pass

    @classmethod
    def mreturn(cls, a):
        # type: (A) -> Monad[A]
        return cls.pure(a)

    def ap(self, m_f):
        # type: (Monad[Callable[A, B]]) -> Monad[B]
        self.apply(m_f)


# Nakedness

def fmap(f, functor_a):
    # type: (Callable[A, B], Functor[A]) -> Functor[B]
    return functor_a.fmap(f)


def id_f(x):
    # type: (A) -> A
    return x


def mjoin(m_m):
    # type: (Monad[Monad[A]]) -> Monad[A]
    return m_m.bind(id_f)


def bind(m_a, f):
    # type: (Monad[A], Callable[A, Monad[B]]) -> Monad[B]
    return m_a.bind(f)


# Utility
class Container(Generic[A]):
    def __init__(self, a):
        self.__value__ = a

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, self.__value__)


# Classics
class Identity(Monad[A], Container[A]):

    def apply(self, f_f):
        # type: (Identity[Callable[A, B]]) -> Identity[B]
        f = f_f.__value__
        return self.pure(self.fmap(f))

    def fmap(self, f):
        # type: (Callable[A,B]) -> Identity[B]
        return Identity(f(self.__value__))

    def bind(self, f):
        # type: (Callable[A,Identity[B]]) -> Identity[B]
        return self.pure(f(self.__value__))

    @classmethod
    def pure(cls, a):
        # type: (A) -> Identity[A]
        return Identity(a)


class Maybe(Monad[A], Monoid[A]):
    @classmethod
    def mzero(cls):
        return Nothing

    def mappend(self, a):
        if isinstance(self, Just) and isinstance(a, Just):
            return self.pure(self.__value__ + a.__value__)
        else:
            return Nothing

    def fmap(self, f):
        # type: (Callable[A,B]) -> Maybe[B]
        if isinstance(self, Just):
            return Just(f(self.__value__))
        else:
            return Nothing

    def bind(self, f):
        # type: (Callable[A,Maybe[B]]) -> Maybe[B]
        if isinstance(self, Just):
            v = f(self.__value__)
            if isinstance(v, Just):
                return Just(f(v))
        return Nothing

    @classmethod
    def pure(cls, t):
        # type: (A) -> Maybe[A]
        return Just(t)

    def apply(self, f_f):
        # type: (Maybe[Callable[A, B]]) -> Maybe[B]
        if isinstance(self, Just) and isinstance(f_f, Just):
            return self.pure(f_f.__value__(self.__value__))
        else:
            return Nothing


class Just(Maybe[A], Container[A]):
    pass


class _Nothing(Maybe[A]):
    def __str__(self):
        return 'Nothing'

Nothing = _Nothing()  # type: Maybe[Any]


class IterM(Iterable[A], Monad[A], Monoid[A], Container[A]):
    @classmethod
    def mzero(cls):
        return IterM([])

    def mappend(self, a):
        return IterM(chain(self, a))

    def bind(self, f):
        # type: (Callable[A, IterM[B]]) -> IterM[B]
        return IterM(y for x in self for y in f(x))

    @classmethod
    def pure(cls, a):
        return IterM([a])

    def apply(self, fs):
        # type: (IterM[Callable[A, B]]) -> IterM[B]
        return IterM(f(x) for f in fs for x in self)

    def fmap(self, f):
        return imap(f, self)

    def __iter__(self):
        return iter(self.__value__)


class ListM(List[A], Monad[A], Monoid[A]):
    @classmethod
    def mzero(cls):
        return ListM([])

    def mappend(self, a):
        return ListM(self + a)

    def bind(self, fs):
        # type: (Callable[A,ListM[B]]) -> ListM[B]
        return ListM(IterM(self).bind(fs))

    @classmethod
    def pure(cls, a):
        return ListM([a])

    def apply(self, f_f):
        # type: (ListM[Callable[A, B]]) -> ListM[B]
        return ListM(IterM(self).apply(f_f))

    def fmap(self, f):
        return map(f, self)