fun-with-semirings.py

# this will work with python 3, but probably not python 2
from functools import reduce

class BoolSemi:
    zero = False
    one = True
    def plus(x, y):
        return x or y
    def times(x, y):
        return x and y
    def star(x):
        return True

def transpose(M):
    # if one of the dimensions is zero, it's impossible to tell what
    # the other dimension is.
    #print(M)
    assert type(M) is list is type(M[0])
    return list(map(lambda *x: list(x), *M))

def split(M):
    left, rest = zip(*[([x], xs) for x,*xs in M[1:]])
    return (
        [[M[0][0]]], [M[0][1:]],
        list(left), list(rest)
    )

def mjoin(A,B,C,D):
    return ([x+y for x,y in zip(A,B)] +
            [x+y for x,y in zip(C,D)])

def matrix(n, R):
    '''Forms the semiring of n-by-n matrices with entries drawn from R.'''
    zero = [[R.zero for _ in range(0,n)] for _ in range(0,n)]
    one = [[R.one if i==j else R.zero for i in range(0,n)] for j in range(0,n)]

    # NB. plus and times will both work for matrices of any size,
    # which is important for the implementation of star to work properly.
    def plus(M, N):
        return [[R.plus(x,y) for x,y in zip(l1,l2)] for l1,l2 in zip(M,N)]

    def times(M, N):
        return [[reduce(R.plus, map(R.times, row, column), R.zero)
                 for column in transpose(N)]
                for row in M]
    multiply = lambda *x: reduce(times,x)
    
    def star(M):
        # print(M)
        if len(M) == 1:
            return [[R.star(M[0][0])]]
        (A,B,C,D) = split(M)
        deltastar = star(plus(D, multiply(C, star(A), B)))
        Cprime = times(C, star(A))
        Bprime = times(star(A), B)
        return mjoin(
            plus(star(A), multiply(Bprime, deltastar, Cprime)),
            times(Bprime, deltastar),
            times(deltastar, Cprime),
            deltastar)

    z,o,p,t,s = zero,one,plus,times,star
    class Matrix:
        zero=z
        one=o
        plus=p
        times=t
        star=s
    return Matrix

## Let's try some examples.
bool_mat = matrix(2,BoolSemi)
cycle = [[False,True],
         [True,False]]
# This should be equal to [[True,True],[True,True]]
cyclestar = bool_mat.star(cycle)
print(cyclestar)