The List monad in Haskell has many uses, including parsing and nondeterministic algorithms. This code implements the Monad combinators "bind", "return" and "fail", and the MonadPlus combinators "plus" and "zero". It works with all iterables, and returns a generator rather than a list in order to preserve a lazy semantics.
Python, 105 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | """Monad combinators for a list/generator monad in Python"""
from itertools import chain
# Infix class by Ferdinand Jamitzky
class Infix:
def __init__(self, function):
self.function = function
def __ror__(self, other):
return Infix(lambda x, self=self, other=other: self.function(other, x))
def __or__(self, other):
return self.function(other)
def __call__(self, value1, value2):
return self.function(value1, value2)
# Monad bind, return, fail and zero
@Infix
def bind(g, f):
for v in g:
for v2 in f(v):
yield v2
@Infix
def mplus(g1, g2):
return chain(g1, g2)
mzero = (v for v in [])
fail = lambda _ : mzero
mreturn = lambda x : (v for v in [x])
# Ambiguous parser example from
# http://www.nomaware.com/monads/html/listmonad.html
class Parsed:
DIGIT="Digit"
HEX="Hex"
WORD="Word"
def __init__(self, tokenType, tokenValue):
self.tokenType = tokenType
self.tokenValue = tokenValue
def __repr__(self):
return "(%s, %s)" % (self.tokenType, str(self.tokenValue))
def parseHexDigit(parsed, char):
if parsed.tokenType==Parsed.HEX:
val = "0123456789ABCDEF".find(char)
if val>-1:
return mreturn(Parsed(Parsed.HEX,
(parsed.tokenValue * 16) + val))
else:
return mzero
else:
return mzero
def parseDigit(parsed, char):
if parsed.tokenType==Parsed.DIGIT:
if char.isdigit():
return mreturn(Parsed(Parsed.DIGIT,
(parsed.tokenValue * 10) + int(char)))
else:
return mzero
else:
return mzero
def parseWord(parsed, char):
if parsed.tokenType==Parsed.WORD:
if char.isalpha():
return mreturn(Parsed(Parsed.WORD,
parsed.tokenValue + char))
else:
return mzero
else:
return mzero
def parse(parsed, char):
return parseHexDigit(parsed, char) |mplus| parseDigit(parsed, char) |mplus| parseWord(parsed, char)
def foldM(p, v, i):
c = i[:1]
cs = i[1:]
if len(i)==1:
return p(v, c)
else:
return p(v, c) |bind| (lambda r : foldM(p, r, cs))
def parseArg(string):
hexParser = mreturn(Parsed(Parsed.HEX, 0))
digitParser = mreturn(Parsed(Parsed.DIGIT, 0))
wordParser = mreturn(Parsed(Parsed.WORD, ""))
parser = hexParser |mplus| digitParser |mplus| wordParser
return parser |bind| (lambda v : foldM(parse, v, string))
|
For an explanation of the Haskell List monad and its uses, see the monad tutorial "All About Monads":
http://www.nomaware.com/monads/html/index.html
The code above includes an implementation of the ambiguous parser example given in that tutorial. This parser will provide a generator iterating over all possible tokens matching an ambiguous string, thus:
>>> list(parseArg("23"))
[(Hex, 35), (Digit, 23)]
>>> list(parseArg("FA"))
[(Hex, 250), (Word, FA)]
>>> list(parseArg("1A"))
[(Hex, 26)]
>>> list(parseArg("Hello"))
[(Word, Hello)]
Tags: algorithms
