Type classes in Python via Dynamic Programming

type_classes_via_dynamic_programming.py

#!/usr/bin/env python2.6

import abc

class Kind(object):
  __metaclass__ = abc.ABCMeta

  kindtypes = dict()
  datatypes = list()

  def __init__(self, instance):
    try:
      assert(True in [isinstance(instance, datatype) for datatype in self.__class__.datatypes])

    except AssertionError as e:
      raise TypeError

    self.identity = instance

  # [a] * (B, a -> b) -> [b]
  @abc.abstractmethod
  def map(self, cls, func):
    return NotImplemented

  # [a] * (B, a -> [b]) -> [b]
  @abc.abstractmethod
  def flatmap(self, cls, func):
    return NotImplemented

  def __str__(self):
    return '%s[%s]' % (self.__class__.__name__, self.identity)

  @classmethod
  def factory(kind, datatype):
    kind_name = kind.__name__ + '_' + datatype.__name__

    if datatype.__name__ not in kind.kindtypes:
      source = 'class %s(%s):\n\tdatatypes = %s.datatypes + [%s]\n' % (
          kind_name, kind.__name__, kind.__name__, datatype.__name__)

      code = compile(source, '<string>', 'exec')
      exec code

      kind.kindtypes[datatype.__name__] = locals()[kind_name]

    return kind.kindtypes[datatype.__name__]

if __name__ == '__main__':
  class Option(Kind):
    datatypes = [type(None)]

    def map(self, func):
      if not self.identity:
        return self

      else:
        result_value = func(self.identity)
        result_type = result_value.__class__

        return Option.factory(result_type)(result_value)

    def flatmap(self, func):
      if not self.identity:
        return self

      else:
        result_value = func(self.identity)
        result_type = result_value.__class__

        try:
          assert(isinstance(result_value, Kind))

        except AssertionError as e:
          raise TypeError

        return result_value

    @classmethod
    def factory(cls, datatype):
      if datatype == type(None):
        return cls

      else:
        return super(Option, cls).factory(datatype)

  class A(object):
    __metaclass__ = abc.ABCMeta

    def __str__(self):
      return 'A'

  class B(A):
    def __str__(self):
      super_str = super(B, self).__str__()
      return '%s->%s' % (super_str, 'B')

  class C(B):
    def __str__(self):
      super_str = super(C, self).__str__()
      return '%s->%s' % (super_str, 'C')

  class D(A):
    def __str__(self):
      super_str = super(D, self).__str__()
      return '%s->%s' % (super_str, 'D')

  b = B()
  c = C()

  some_b = Option.factory(B)(b)
  some_c = Option.factory(C)(c)

  none = Option.factory(B)(None)

  print b
  print c
  print some_b
  print some_c
  print none

  # supports covariance
  some_other_c = Option.factory(B)(c)

  # supports functional map 
  some_other_c = some_b.map(lambda x: C())

  print some_other_c

  some_other_c = some_b.map(lambda x: None)

  print some_other_c

  another_none = some_b.flatmap(lambda x: none)

  print another_none

  try:
    # does not support contravariance
    Option.factory(C)(b)
  except TypeError as e:
    print 'Type constructors do not support contravariance'

  try:
    # support only invariant or covariant types
    Option.factory(D)(b)
  except TypeError as e:
    print 'Type constructors must be given invariant or covariant types'

  try:
    Kind(A)
  except TypeError as e:
    print '`Kind` is an abstract class.'

  # memoize classes after execution
  # only one class created per generic implementation request
  # also can do at application bootstrap via iteration thru module of implementable types
  assert(len(Option.kindtypes) == 3)
  Option.factory(B)
  assert(len(Option.kindtypes) == 3)