Welcome, guest | Sign In | My Account | Store | Cart

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
 ``` 1 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":

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)]
``````
 Created by Dominic Fox on Thu, 18 Aug 2005 (PSF)