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
  end

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

  def self.unit(val)
    self.new([val])
  end

  def to_s
    joined = array.join(', ')
    "ListMonad([#{joined}])"
  end
end

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

class Array
  def bind(bindee)
    ListMonad.new(self).bind(bindee)
  end

  def bindb(&block)
    ListMonad.new(self).bindb(&block)
  end
end
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
end

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
  end
end

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

    @classmethod
    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]

@do(ListMonad)
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|
    begin
      checked_callcc do |outer_cont|
        monad.bindb do |val|
          callcc do |inner_cont|
            finishers.push(inner_cont)
            outer_cont.call(val)
          end
        end
      end
    rescue ContinuationUnused => unused
      raise MonadEscape.new(unused.result)
    end
  end

  val = begin
    monad_class.maybeUnit(block.call(rbind_ext))
  rescue MonadEscape => escape
    escape.monad
  end

  finisher = finishers.pop()
  if finisher
    finisher.call(val)
  else
    val
  end
end

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

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:
                self.iterator.send(value)
        return self.iterator
            
    def send(self, value):
        iterator = self.getIterator()
        self.log.append(value)
        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:

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

        if isinstance(itr, types.GeneratorType):
            @handle_monadic_throws(Monad)
            def send(itr, val):
                try:
                    # 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)
        else:
            #not really a generator
            if itr is None:
                return Monad.unit(None)
            else:
                return itr

    return run_maybe_iterator()

@do_ext(ListMonad)
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:

@do_ext(ListMonad)
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.

63 comments:

  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:

    http://repo.or.cz/w/ruby-do-notation.git

    ReplyDelete
    Replies
    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

      Delete
  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.

    ReplyDelete
  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/

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

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

    ReplyDelete
  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.

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  13. "Very Nice Blog!!!


    Please have a look about "
    data science malaysia

    ReplyDelete
  14. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data analytics courses in bangalore

    ReplyDelete
  15. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    cyber security training in bangalore

    ReplyDelete
  16. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging endeavours.
    data science institute in bangalore

    ReplyDelete
  17. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging endeavours.
    data science course in bangalore with placement

    ReplyDelete
  18. Great post i must say and thanks for the information. Education is definitely a sticky subject. However, is still among the leading topics of our time. I appreciate your post and look forward to more.
    Data Science Course in Bangalore

    ReplyDelete
  19. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    cyber security training in bangalore

    ReplyDelete
  20. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Training in Chennai

    ReplyDelete
  21. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    cyber security training in bangalore

    ReplyDelete
  22. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data analytics courses in bangalore

    ReplyDelete
  23. I just got to this amazing site not long ago. I was actually captured with the piece of resources you have got here. Big thumbs up for making such wonderful blog page!
    data analytics course in bangalore

    ReplyDelete
  24. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    data science course

    ReplyDelete
  25. Seeking for the Physics Assignment Help ? If yes then have a look here.

    ReplyDelete
  26. This is most informative and also this post most user friendly and super navigation to all posts... Thank you so much for giving this information to me..
    machine learning certification in aurangabad

    ReplyDelete
  27. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data science course fees in bangalore

    ReplyDelete
  28. Thanks for posting the best information and the blog is very important.digital marketing institute in hyderabad

    ReplyDelete
  29. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Course Syllabus

    ReplyDelete
  30. I am a new user of this site, so here I saw several articles and posts published on this site, I am more interested in some of them, hope you will provide more information on these topics in your next articles.
    data analytics training in bangalore

    ReplyDelete
  31. Your content is very unique and understandable useful for the readers keep update more article like this.
    data science course aurangabad

    ReplyDelete
  32. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    artificial intelligence training in chennai

    ReplyDelete
  33. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such amazing content for all the curious readers who are very keen on being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in the future too.

    Digital Marketing Training in Bangalore

    ReplyDelete
  34. I wanted to leave a little comment to support you and wish you the best of luck. We wish you the best of luck in all of your blogging endeavors.

    Artificial Intelligence Training in Bangalore

    ReplyDelete
  35. Truly incredible blog found to be very impressive due to which the learners who go through it will try to explore themselves with the content to develop the skills to an extreme level. Eventually, thanking the blogger to come up with such phenomenal content. Hope you arrive with similar content in the future as well.

    Machine Learning Course in Bangalore

    ReplyDelete
  36. You have completed certain reliable points there. I did some research on the subject and found that almost everyone will agree with your blog.

    Data Science Training in Bangalore

    ReplyDelete
  37. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Course Syllabus

    ReplyDelete
  38. Truly mind blowing blog went amazed with the subject they have developed the content. These kind of posts really helpful to gain the knowledge of unknown things which surely triggers to motivate and learn the new innovative contents. Hope you deliver the similar successive contents forthcoming as well.

    Data Science in Bangalore

    ReplyDelete
  39. Impressive. Your story always bring hope and new energy. Keep up the good work.
    best data science institute in hyderabad

    ReplyDelete
  40. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    artificial intelligence training in chennai

    ReplyDelete
  41. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data science training in chennai

    ReplyDelete
  42. Our Criminology Assignment Help assists students all over the USA get the most excellent support at a minimal cost. As you progress through the task, you will be assisted by top-notch professionals who will provide you with valuable comments and guidance.

    ReplyDelete
  43. Thanks for sharing this informative content.,
    Leanpitch provides online training in Scrum Master Certification during this lockdown period everyone can use it wisely.
    Join Leanpitch 2 Days CSM Certification Workshop in different cities.

    Scrum master certification online

    CSM certification online

    CSM online

    CSM online certification

    CSM online training

    CSM training online

    Scrum master training online

    ReplyDelete
  44. Very awesome!!! When I seek for this I found this website at the top of all blogs in search engine.
    data science training in malaysia

    ReplyDelete
  45. First You got a great blog .I will be interested in more similar topics. i see you got really very useful topics, i will be always checking your blog thanks.
    data scientist certification malaysia

    ReplyDelete
  46. Very interesting to read this article. I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. Keep it up.
    AWS Training in Hyderabad
    AWS Course in Hyderabad

    ReplyDelete
  47. Good post! Interesting content, well written. Really enjoyed the read and your breakdown of our product helped clarify some questions I was wondering about.
    Data Science Training in Hyderabad
    Data Science Course in Hyderabad

    ReplyDelete
  48. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    data science training in malaysia

    ReplyDelete
  49. If more people that write articles really concerned themselves with writing great content like you, more readers would be interested in their writings. Thank you for caring about your content. Also visit my website: 바카라사이트

    ReplyDelete
  50. Your content is nothing short of brilliant in many ways. I think this is engaging and eye-opening material. Thank you so much for caring about your content and your readers Also visit my website: 바카라사이트

    ReplyDelete
  51. Hey, I am so thrilled I found your blog, I am here now and could just like to say thank for a tremendous post and all round interesting website. Please do keep up the great work. I cannot be without visiting your blog again and again. Also visit my website: 바카라

    ReplyDelete
  52. Impressive. Your story always bring hope and new energy. Keep up the good work.
    data scientist course in malaysia

    ReplyDelete

Blog Archive

Google Analytics