coder . cl

On a recent post on his blog, Francisco Mota has described Monoids with both, the Mathematical background and the functional background. If you read careful the post, you will notice that he has created the Monoid class. He describes a Monoid as a set with neutral element and an the operation , where the triple denotes the Monoid. In terms of Category Theory, the set should be a category and the operation should be a morphism.

Some examples of Monoids, should be , , and so on, to describe some operations that should be mapped to natural numbers. Applied to the Python programming language, he describes sets as lists or tuples, and Python data types as Categories to treat certain operations as Monoids. Francisco has proposed a set of challenges regarding Monoids in Python. Here I will describe some solutions to those challenges.

1. Using only listm, how would you concatenate a list of lists. That is, how would you transform [[a, b, c], [d, e], [f], []] into [a, b, c, d, e, f]?
2. The reverse of a monoid is a monoid where the operator take its arguments in reverse order. Create a method, reverse, that creates a reverse monoid. What is listm.reverse()?
3. Are there monoids that are fixed-points of the star method? That is, is there a monoid m such that m and m.star() are indistinguishable? (Side challenge: formalize the notion of “indistinguishable”.)
4. Do monoids have a dual concept? Monoids, as defined here, are roughly an embodiment of “map/reduce”, which is used to process and analyze data, potentially taking a large body of data and reducing it. Is there a similar concept, a “comonoid”, that generates data, instead of reducing it?
5. Let lift = int, and let op return an int. Can we enumerate all possible monoids? If not, what can we enumerate?

the final monoid class

class Monoid(object):
    null = None
    lift = None
    op = None

    def __init__(self, null, lift, op):
        self.null = null
        self.lift = lift
        self.op = op

    def fold(self, xs):
        if hasattr(xs, '__fold__') and callable(xs.__fold__):
            return xs.__fold__(self)
        else:
            mxs = map(self.lift, xs)
            return reduce(self.op, mxs, self.null)

    def rfold(self, xs):
        def reverse_reduce(op, lst, null):
            acm = null
            if len(lst) <= 0:
                return acm
            cnt = 0
            lim = len(lst) - 1
            while cnt < lim:
                acm = op(lst[cnt], acm)
                cnt += 1
            return op(lst[lim], acm)
        mxs = map(self.lift, xs)
        return reverse_reduce(self.op, mxs, self.null)

    def __call__(self, *args):
        return self.fold(args)

    def star(self):
        return Monoid(self.null, self.fold, self.op)

    def reverse(self):
        class ReverseMonoid(Monoid):
            def __call__(self, *args):
                return self.rfold(*args)
            def star(self):
                return ReverseMonoid(self.null, self.rfold, self.op)
        return ReverseMonoid(self.null, self.lift, self.op)

1. listm as list concatenator

## challenge 1

listm = Monoid([], lambda x: [x], lambda a, b: a + b)
sample_list = [['a', 'b', 'c'], ['d', 'e'], ['f'], []]
a = listm.star().fold(sample_list)
print("a = %s" % (repr(a)))

## end challenge 1

2. reverse litsm monoid

A reverse Monoid, takes the operation arguments on reverse order, instead of passing a, b, it uses b, a as operation arguments on the reduce function. The reverse() method returns a ReverseMonoid instance.

## challenge 2

listmr = listm.reverse()
b = listmr(a)
print("---> Challenge 2.")
print("b = %s" % (repr(b)))

## end challenge 2

3. fixed-point monoids

A fixed-point monoid to its star() method requires a fold() or reduction method returning the same type as its arguments. The only type that allows such stuff in native Python is the string, so we will use the string type related Monoid to define a fixed-point Monoid to its star() method. The joinm monoid meets that requirement.

### challenge 3.1

sample_string1 = "hello 1!"
sample_string2 = "hello 2!"
sample_string3 = "hello 3!"

joinm = Monoid('', lambda x: str(x), lambda a, b: a + b)

sjoinm  = joinm.star()
rjoinm = joinm.reverse()

print("---> Challenge 3.2")

c0 = joinm(sample_string1,
           sample_string2,
           sample_string3)
print("c0 = %s" % (repr(c0)))

c1 = sjoinm(sample_string1,
            sample_string2,
            sample_string3)
print("c1 = %s" % (repr(c1)))

## end challenge 3

The example above, should be formalized as . Other example can be implemented using some type checking tricks.

## challenge 3.2

def sum_list(x):
    return ([lambda n: sum(n),
             lambda m: m][cmp(type(x),
                              list)])(x)

def reduce_list(a, b):
    return ([lambda n: sum(n),
             lambda m: m][cmp(type(a),
                              list)])(a) 
           + ([lambda n: sum(n),
               lambda m: m][cmp(type(b),
                                list)])(b)

sample_list = [1, 2, 3, 4, 5]

summ = Monoid(0, sum_list, reduce_list)
ssumm  = summ.star()
rsumm = summ.reverse()

print("---> Challenge 3.1")

c0 = summ(sample_list)
print("c0 = %s" % (repr(c0)))

c1 = ssumm(sample_list)
print("c1 = %s" % (repr(c1)))

c2 = rsumm(sample_list)
print("c2 = %s" % (repr(c2)))

## end challenge 3.2

4. comonoid using monoid constructor

## challenge 4

def sum_list(x):
    return range(0, ([lambda n: sum(n),
                      lambda m: m][cmp(type(x),
                                       list)])(x))

def reduce_list(a, b):
    return range(0, ([lambda n: sum(n),
                      lambda m: m][cmp(type(a),
                                       list)])(a) 
                 + ([lambda n: sum(n),
                     lambda m: m][cmp(type(b),
                                      list)])(b))

### challenge 4
sample_list = [1, 2, 3, 4, 5]
summ = Monoid(0, sum_list, reduce_list)
ssumm  = summ.star()
rsumm = summ.reverse()

print("---> Challenge 4")

c0 = summ(sample_list)
print("c0 = %s" % (repr(c0)))

c1 = ssumm(sample_list)
print("c1 = %s" % (repr(c1)))

c2 = rsumm(sample_list)
print("c2 = %s" % (repr(c2)))

## end challenge 4

5. enumerate int monoids

Since the number of operations that can be made using the int type in Python, we cannot enumerate such set of monoids. Such monoid, that should be declared as Monoid (0, lambda x: int(x), f), where f can be any function returning int. The only set that we can enumerate is the limited number of integer numbers that can operate with f. I hope that you will enjoy the examples above.