I've learned. I'll share.

January 15, 2008

List Monad in Ruby and Python

Recently, I wrote about ways to add something like Haskell's do syntax to programming languages like python and ruby. The python trick used bidirectional generators and the ruby trick used callcc. I have since been notified that there is one serious problem with both of them: the bindee (the function given to bind) can only be called once. For many monads, this limitation is acceptable, but for some, it means you can't use that nice syntax.

Take the List monad, for example, in ruby:

class ListMonad < Monad
  attr_accessor :array

  def initialize(array)
    @array = array

  def bind(bindee)
    ListMonad.new(concat(array.map { |val| maybeUnit(bindee.call(val)).array }))

  def self.unit(val)

  def to_s
    joined = array.join(', ')

## I'm hoping this if faster than using fold (inject)
def concat(arrays)
  all = []
  for array in arrays
    all += array

class Array
  def bind(bindee)

  def bindb(&block)
Ruby gives us the ability to extend Array to get a pretty sweet looking use of the monad:
list1 = with_monad ListMonad do
  x =xx    [1,2,3]
  y =xx [10,20,30]
  x + y

It looks great, but list1 should be ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]), be we get ListMonad([11]) instead.

Traditional binding works fine:

list2 = [1, 2, 3].bindb do |x|
  [10, 20, 30].bindb do |y|
    x + y

list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). So, we know our monad is fine, but our with_monad doesn't work.

We have the same problem in python:

class ListMonad(Monad):
    def __init__(self, vals):
        self.vals = vals

    def bind(self, bindee):
        return self.__class__(concat((self.maybeUnit(bindee(val)) for val in self.vals)))

    def unit(cls, val):
        return cls([val])

    def __repr__(self):
        return "ListMonad(%s)" % self.vals

    def __iter__(self):
        return iter(self.vals)

def concat(lists):
    return [val for lst in lists
                for val in lst]

def with_list_monad():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list1 = with_list_monad()

def with_list_monad_binding():
    return \
    ListMonad([  1, 2, 3])  >> (lambda x:
    ListMonad([10, 20, 30]) >> (lambda y:
    x + y))

list2 = with_list_monad_binding()

Again, it looks good, but list1 is ListMonad([11, None, None, None, None]) while list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The result of list1 sure is bizarre.

Luckily, I have found a solution for ruby, and a bad hack that could be construed as a solution for python if you ignore some issues.

In Ruby, the trick is to monkey with the rbind continuation so that at the end of with_monad it returns control to the point where the continuation is called. In other words, we need to store a second continuation at the point right after the first continuation is called. Confused yet? Continuations will melt your brain, and this took a little while for met get right:

def with_monad_ext(monad_class, &block)
  finishers = []

  rbind_ext = lambda do |monad|
      checked_callcc do |outer_cont|
        monad.bindb do |val|
          callcc do |inner_cont|
    rescue ContinuationUnused => unused
      raise MonadEscape.new(unused.result)

  val = begin
  rescue MonadEscape => escape

  finisher = finishers.pop()
  if finisher

list3 = with_monad_ext ListMonad do |rbind|
  x = rbind.call    [1,2,3]
  y = rbind.call [10,20,30]
  x + y

Success! list3 is correctly ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The only real problem is that the normal rbind won't work. We have to make a special one and give it to the block as an argument. This wouldn't be that bad, except that Ruby has this silly limitation so we have to say rbind.call rather than just rbind, which makes it less fun to type. I named it with_monad_ext because I don't think it will be needed as often as with_monad, and with_monad is more convenient.

Now, back to python. The problem is harder. It's rooted in the fact that for a given iterator, itr.send() is not reentrant. But, if we could copy the iterator, that would give us a possible solution. I did a little googling and found that python isn't going to have copy.copy(itr) anytime soon because no one cares about them. Some people have made some progress, but it segfaults on my computer (64-bit Linux, in case you're wondering).

So, I came up with this terrible little hack which makes it possible to "copy" iterators:

class CopyableIterator:
    def __init__(self, generator, log = ()):
        self.generator = generator
        self.log       = list(log) #hmmm... if the logs were immutable, we wouldn't have to do this
        self.iterator  = None

    def getIterator(self):
        if self.iterator is None:
            self.iterator = self.generator()
            for value in self.log:
        return self.iterator
    def send(self, value):
        iterator = self.getIterator()
        return iterator.send(value)

    def next(self):
        return self.send(None)

    def copy(self):
        return self.__class__(self.generator, self.log)

That let's us define @do_ext:

def do_ext(func, func_args, func_kargs, Monad):
    def run_maybe_iterator():
        itr = func(*func_args, **func_kargs)

        if isinstance(itr, types.GeneratorType):
            def send(itr, val):
                    # here's the real magic
                    monad = Monad.maybeNew(itr.send(val))
                    return monad.bind(lambda val : send(itr.copy(), val))
                except StopIteration:
                    return Monad.unit(None)
            return send(CopyableIterator(lambda : func(*func_args, **func_kargs)), None)
            #not really a generator
            if itr is None:
                return Monad.unit(None)
                return itr

    return run_maybe_iterator()

def with_list_monad_ext():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list3 = with_list_monad_ext()

And list3 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23]). Success again! There is a downside, though. First, all of the calculations are done for all of the combinations. This is especially bad if you do this:

def with_list_monad_ext():
    print "foo"
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

Because now you'll print "foo" 9 times instead of 1.

So there you have it: you can do the List monad with do syntax in python and ruby, but you'll have to decide whether the trade-offs are worth it.


  1. Does it go up to 3 or more invocations? I'm having difficulty getting all your code together to try it myself.

    For the record, here's my ParseTree version, which now supports the arrow "operator" and is nestable:


  2. Bạn đang muốn đi du lịch ở Đà Nẵng. Bạn đang đi tìm kiếm kinh nghiệm du lịch Đà Nẵng để có thể học hỏi áp dụng. Hãy ghé vào Villa Đà Nẵng để có thể xem qua những kinh nghiệm du lịch và thông tin liên quan mà chúng tôi cung cấp cho bạn nhé. Ngoài ra chúng tôi cũng đang cung cấp dịch vụ cho thuê villa - biệt thự ở đà nẵng đảm bảo giá cả rẻ hơn các nơi khác. Nếu có nhu cầu hãy liên lạc với chúng tôi nhé. Đảm bảo chúng tôi sẽ không làm bạn thất vọng.

  3. Change is absolutely constant. Even education are adapting to the change; from traditional education now comes the online education. This latest system of learning is exciting as well as it is time and money efficient. In fact, it is now a growing trend worldwide. Many people consider this because it's easy access and has budget-friendly requirements without sacrificing quality education.http://www.thesisexample.info/


Blog Archive

Google Analytics