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

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

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)]

Add a comment

Sign in to comment

Created by Dominic Fox on Thu, 18 Aug 2005 (PSF)
Python recipes (4190)
Dominic Fox's recipes (4)

Required Modules

Other Information and Tasks