A practice of Algebraic Data Type implementation in Python

algebraic_data_type.py

# python3.6 -m doctest algebraic_data_type.py

"""
A practice that implement algebraic data type in Python.

> data Maybe a = Just a | Nothing

Usage of `Maybe`:

>>> Just(3)
Just 3
>>> Just(3).__class__
<class 'algebraic_data_type.Maybe int'>
>>> Just(3).constructor
<bound method Maybe.just of <class 'algebraic_data_type.Maybe'>>
>>> Just(3)._a
3
>>> Just(3)._argument_classes
{'a': <class 'int'>}
>>> Just(3) == Just(1), Just(3) == Just(3)
(False, True)
>>> fmap(lambda x:x**3, Nothing())
Nothing
>>> fmap(lambda x:x**3, Just(3))
Just 27


f : Maybe a → Maybe a
f Nothing = Nothing

g : Maybe a → Maybe a
g _ = Nothing

h : Maybe Int → Maybe Int
h _ = Just 2

>>> h(g(f(Nothing())))
Just 2
"""


class Mock:
    pass


def generate_name(_c = __import__('itertools').count()):
    return 'a' + str(next(_c))


def wrap_str(tn, n):
    """
    this function should be enhanced to support abstract data type with
    multiple arguments like "M a b c" in the future
    """
    return f'{tn} ({n})' if ' ' in n else f'{tn} {n}'


class Maybe(type):
    _classes = {}

    def _instantiate(tcls, cls, constructor, a=None):
        """
        add requirements onto instance
        """
        instance = cls()
        instance.constructor = constructor
        if constructor == tcls.just:
            instance._a = a
        return instance

    @classmethod
    def just(tcls, a, base=None):
        """
        `just` constructor
        """
        if base is not None:
            cls = base
        else:
            cls = tcls._classes.setdefault(a.__class__, tcls(a.__class__))
        return tcls._instantiate(tcls, cls, tcls.just, a)

    @classmethod
    def nothing(tcls, base=None):
        """
        `nothing` constructor
        """
        if base is not None:
            cls = base
        else:
            cls = tcls(type(generate_name(),(Mock,),{}))
        return tcls._instantiate(tcls, cls, tcls.nothing)

    def __new__(tcls, cls):
        name = wrap_str(tcls.__name__, cls.__name__)
        return tcls._classes.setdefault(name, type.__new__(tcls, name, (), {
            '_argument_classes': {'a': cls} ,
            '__repr__': lambda s: \
                'Nothing' if s.constructor == tcls.nothing else wrap_str('Just',repr(s._a)) ,
            '__eq__': lambda s, a: \
                s.constructor == a.constructor and (s._a == a._a if hasattr(s, '_a') else True),
            '_fmap': lambda s, f: \
                    tcls.nothing() if s.constructor == tcls.nothing else tcls.just(f(s._a)) ,
             }))


Just = Maybe.just
Nothing = Maybe.nothing


def fmap(f, fa):
    """
    functor map
    """
    return fa._fmap(f)


def f(n):
    """
    f : Maybe a → Maybe a
    f Nothing = Nothing

    >>> f(3)
    Traceback (most recent call last):
    TypeError
    >>> f(Nothing())
    Nothing
    >>> f(Just(3))
    Traceback (most recent call last):
    NotImplementedError
    """
    if not isinstance(n.__class__, Maybe):
        raise TypeError

    if n.constructor == Nothing:
        return n
    else:
        raise NotImplementedError


def g(x):
    """
    g : Maybe a → Maybe a
    g _ = Nothing

    >>> g(3)
    Traceback (most recent call last):
    TypeError
    >>> j, n = Just(3), Nothing()
    >>> g(j) == g(n)
    True
    >>> g(n).constructor == Nothing
    True
    >>> g(n) is n , g(n).__class__ is n.__class__
    (False, True)
    """
    if not isinstance(x.__class__, Maybe):
        raise TypeError

    return Nothing(base=x.__class__)


def h(x):
    """
    h : Maybe Int → Maybe Int
    h _ = Just 2

    >>> n = Nothing()
    >>> n._argument_classes['a'] is not int
    True
    >>> j = h(n)
    >>> j._argument_classes['a'] is int and j._a is 2
    True
    """
    if not isinstance(x.__class__, Maybe):
        raise TypeError
    elif x._argument_classes['a'] != int and issubclass(x._argument_classes['a'], Mock):
        MaybeInt = Maybe(int)
        x.__class__ = MaybeInt
        x._argument_classes = (int,)
    else:
        raise TypeError

    return Just(2, base=x.__class__)