Records and pattern matching

##record.py
##
##"record" is an implementation of a simple record
##type constructor for records with labeled fields.
##The record types will be subclasses of "tuple".
##
##"match" is a pattern matcher for matching patterns
##of complex record structures to a record object and
##binding elements in the matched structure to parameters
##in a handler function.
##
##Example:
##from record import record, match, sym
##tree = record(sym.tree, sym.left, sym.right)
##def flatten(t):
##    return (match(t).
##    case(tree(sym.left, sym.right),
##          lambda left, right: flatten(left)+flatten(right)).
##    case(sym.leaf, lambda leaf: [leaf])
##    ())
##
##t = tree(tree(1, tree(2, 4)), 3)
##print flatten(t)
##prints:
##[1, 2, 4, 3]


class symbol(object):
    """
    Symbols for place holders for pattern matching
    """
    syms = {}
    
    def __new__(kls, name):
        if name in symbol.syms:
            return symbol.syms[name]
        else:
            o = object.__new__(kls)
            symbol.syms[name] = o
            return o
        
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

class _symbol(object):
    def __getattribute__(self, name):
        return symbol(name)

sym = _symbol()

def record(name, *labels):
    """
    Construct a record type. Records are subclasses of tuple:
    <new record class> = record(name, label1, ...)
    
    Usage:
    user = record(sym.user, sym.name, sym.password)
    ram = user(name="ram", password="*****")
    shyam = user("shyam", "*")
    print "ram's name = ", ram.name
    name, password = ram
    """
    labels = [str(label) for label in labels]
    name = str(name)
    def new(kls, *labels):
        return tuple.__new__(kls, labels)
    def __str__(self):
        return "%s(%s)" % (name,
                           ", ".join(("%s=%s"%(label, val)
                                      for label, val
                                      in zip(labels, self))))
    d = {"__new__":new,
         "__str__":__str__,
         "__repr__":__str__}
    exec ("""def __init__(self, %s):pass""" %
          ", ".join(labels)) in d
    
    for i in range(len(labels)):
        d[labels[i]] = (lambda i:
                        property(lambda self:
                                 self[i]))(i)

    return type(name, (tuple,), d)

def _combine(obj, pattern):
    if isinstance(pattern, symbol):
        return [(str(pattern), obj)]
    elif isinstance(pattern, tuple) and type(obj)==type(pattern):
        return sum((_combine(o, p) for o, p in zip(obj, pattern)), [])
    elif pattern == obj:
        return []
    else:
        return False

class MatchFailed(Exception):pass       

class match(object):
    """
    Match the given object and do some actions
    """
    def __init__(self, obj):
        self.obj = obj
        self.matchers = []
        def onDefault(obj):
            raise MatchFailed
        self._onDefault = onDefault
        
    def case(self, pattern, onMatch):
        """
        Add a match case.
        
        The match case matches a pattern to an action
        """
        self.matchers.append((pattern, onMatch))
        return self

    def default(self, onDefault):
        """
        Set a default handler if all matches fail.
        
        The handler must accept one parameter which
        will be the match object.
        """
        self._onDefault = onDefault

    def __call__(self):
        """
        Execute the match
        """
        for pattern, onMatch in self.matchers:
            c = _combine(self.obj, pattern)
            if c!=False:
                return onMatch(**dict(c))
        self._onDefault(self.obj)

Two way iterator

#twowayiterator.py
#
#Helpers for implementing iterators
#that can be talked to
#
#See:
#http://blogs.applibase.net/sidharth/?p=30
#

def izip(*args):
    """
    A special version of izip
    that continues processing the
    remaining iterators one more
    time even after the one of them
    has thrown StopIteration.
    """
    iters = [arg for arg in args]
    canloop = True
    while canloop:
        l = []
        for it in iters:
            if canloop:
                try:
                    l.append(it.next())
                except StopIteration:
                    canloop = False
            else:
                try:
                    it.next()
                except StopIteration:
                    pass
        if canloop:
            yield l

class _Ref:
    def put(self, val):
        self.val = val
    def get(self):
        return val

class _Ret:
    def set(self, val):
        self.val = val
        raise StopIteration
    
    def get(self):
        return self.val

def twowayiterator(generator):
    """
    A decorator for generators for iterators
    that can get messages from the caller.

    Building a generator:
    @twowayiterator
    def <generator_name>((ret, get), <params>):
        ...
        yield <value>
        <var>=get()
        ...
        ret(<value>)
        
    ret and get are required parameters for the decorator
    get is used to return the value injectd into the
    iterator by its caller.
    yield <value>
    <var>=get()
    could be considered to represent
    <var>=yield<value>

    ret is used to signal that the iterator is done and
    return a value to its caller.
    ret(<value>)
    could be represented as
    return <value>

    Using a two way iterator
    (ret, put), iter = <generator_name>(<params>)
    try:
        ...
        put(<value>)
        <var>=iter.next()
        ...
    except StopIteration:
        ...
    <var>=ret()

    put is used to inject a value into the iterator
    it is the other side of the get function
    put(<value>)
    <var>=iter.next()
    can be represented as
    <var>=iter.next(<value>)

    ret in this case case is different from ret in the
    iterator it is used to recieve a value returned
    using ret.

    The two way iterator could be used in a for loop
    
    (ret, put), iter = <generator_name>(<params>)
    for val in iter:
        ...
        put(<value>)
    <var>=ret()
    """
    def _twowayiterator(*args, **aargs):
        _in = _Ref()
        ret = _Ret()
        return ((ret.get, _in.put),
                generator((ret.set, _in.get),
                          *args, **aargs))
    return _twowayiterator

Tree Function examples

#trees.py
#
#See Roshan's blog
#

from itertools import izip

class Node:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return "Node(%s, %s)"%(self.left, self.right)

def flatten(node):
    """
    Flatten the tree depth first from the left to right.
    """
    if isinstance(node, Node):
        for i in flatten(node.left):
            yield i
        for i in flatten(node.right):
            yield i
    else:
        yield node

def samefringe(tree1, tree2):
    """
    Check whether two trees have the same leaf nodes
    with the same value.
    """
    for leaf1, leaf2 in izip(flatten(tree1), flatten(tree2)):
        if leaf1!=leaf2:
            return False
    return True


def repmin(tree):
    """
    Return a new tree in with the same node structure
    but all leaf nodes have the same value which is the
    minimum leaf value.
    """
    minval, f = _repmin(tree)
    return f(minval)

def _repmin(tree):
    if isinstance(tree, Node):
       (minleft, left) = _repmin(tree.left)
       (minright, right) = _repmin(tree.right)
       return (min(minleft, minright),
               lambda minval: Node(left(minval), right(minval)))
    else:
        return (tree, lambda val: val)

tree1 = Node(1, Node(2, Node(3, Node(4, 5))))
tree2 = Node(Node(1, Node(2, 3)), Node(4, 5))
tree3 = Node(Node(1, Node(2, 4)), Node(4, 5))

print samefringe(tree1, tree2)
print samefringe(tree1, tree3)

print repmin(tree1)