monad.py

from abc import ABC, abstractmethod
from typing import Callable, Generic, Iterable, Iterator, Optional, Tuple, TypeVar, Union

T = TypeVar('T')
U = TypeVar('U')

class Functor(ABC, Generic[T]):
    @abstractmethod
    def fmap(self, f: Callable[[T], U]) -> 'Functor[U]':
        raise NotImplemented

class Applicative(Functor[T]):
    @staticmethod
    @abstractmethod
    def pure(value: T) -> 'Monad[T]':
        raise NotImplemented

    @abstractmethod
    def apply(self, builder: 'Applicative[Callable[[T], U]]') -> 'Applicative[U]':
        raise NotImplemented

class Monad(Applicative[T]):
    @abstractmethod
    def bind(self: 'Monad[T]', f: Callable[[T], 'Monad[U]']) -> 'Monad[U]':
        raise NotImplemented


class Maybe(Generic[T]):
    def __init__(self, value: Optional[T] = None):
        self.value: Union[T, None] = value

    def __iter__(self):
        if self.value:
            yield self.value

    @staticmethod
    def none() -> 'Maybe[T]':
        return Maybe()

    @staticmethod
    def some(value: T) -> 'Maybe[T]':
        return Maybe(value)

    def fmap(self, f: Callable[[T], U]) -> 'Maybe[U]':
        match self.value:
            case None:
                return Maybe()
            case value:
                return Maybe(f(value))

    @staticmethod
    def pure(value: T) -> 'Maybe[T]':
        return Maybe(value)

    def bind(self, f: Callable[[T], 'Maybe[U]']) -> 'Maybe[U]':
        match self.value:
            case None: return Maybe()
            case value: return f(value)

Monad.register(Maybe)


class List(Generic[T]):
    def __init__(self, cons: Optional[Tuple[T, 'List[T]']] = None):
        self.cons: Optional[Tuple[T, 'List[T]']] = cons

    def __iter__(self) -> Iterator[T]:
        cons = self.cons
        while cons:
            head, tail = cons
            cons = tail.cons
            yield head

    @staticmethod
    def from_iter(it: Iterable[T]) -> 'List[T]':
        elems = list(it)
        ret: 'List[T]' = List()
        for el in reversed(elems):
            ret = List((el, ret))
        return ret

    def fmap(self, f: Callable[[T], U]) -> 'List[U]':
        us: list[U] = []
        for el in self:
            us.append(f(el))
        result: List[U] = List()
        for u in reversed(us):
            result = List((u, result))
        return result

    @staticmethod
    def pure(value: T) -> 'List[T]':
        return List((value, List()))

    def bind(self, f: Callable[[T], 'List[U]']) -> 'List[U]':
        result: list[U] = []
        cons = self.cons
        while True:
            match cons:
                case None:
                    break
                case head, tail:
                    cons = tail.cons
                    for u in f(head):
                        result.append(u)
        other: 'List[U]' = List()
        for elem in reversed(result):
            other = List((elem, other))
        return other

Monad.register(List)


if __name__ == '__main__':
    j4 = Maybe(4)
    assert list(j4.bind(lambda x: Maybe(x + 2))) == [6]
    #assert j4.bind(lambda x: x), None

    lst: List[int] = List.from_iter([1, 2, 3])
    assert list(lst) == [1, 2, 3]
    
    assert list(lst.bind(lambda x: List.from_iter([x, x]))) == [1, 1, 2, 2, 3, 3]