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:


    1. I am glad that I saw this post. It is informative blog for us and we need this type of blog thanks for share this blog, Keep posting such instructional blogs and I am looking forward for your future posts. Python Projects for Students Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account. Project Center in Chennai

  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/

  4. You can easily thin of good title of essay using these advice's

  5. Hello! I just read this information and i can tell you that this article is useful. Thank you for sharing it.

  6. These programming languages are very important for developers because through using these programming, they make different websites and software. I have also learn ruby and working on an educational project. Dissertation writing services.

  7. Very good writings. Maybe someone know, where can I find top rated essay writing service? This post wrote good professional, which knows own work. And I need help with my essay, something like this article. Cheap Hardware Install Services in Dubai

  8. Great article with valuable information found very resourceful and enjoyed reading it waiting for next blog updated thanks for sharing.
    typeerror nonetype object is not subscriptable

  9. I was browsing the internet for information and found your blog. I am impressed with the information you have on this blog.

    Business Analytics Course in Bangalore

  10. Actually I read it yesterday but I had some ideas about it and today I wanted to read it again because it is so well written.

    Data Analytics Course in Bangalore

  11. Attend The Data Analyst Course From ExcelR. Practical Data Analyst Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analyst Course.
    Data Analyst Course

  12. I have to search sites with relevant information ,This is a
    wonderful blog,These type of blog keeps the users interest in
    the website, i am impressed. thank you.
    Data Science Training in Bangalore

  13. "Very Nice Blog!!!

    Please have a look about "
    data science malaysia


Blog Archive

Google Analytics