Powerset in Ruby Using the List Monad

While trying to think of good, quick interview questions I stumbled across power set (thanks to Mike DiStaula for suggesting it). After 10 minutes of hacking in Ruby I discovered that it’s not a reasonable replacement for our current starter question (it takes too long), but it’s also a fun problem to solve.

Then I wandered across this definition of power set in Haskell:

powerset = filterM (const [True, False])

Well, that was easy. So I set out to write that in Ruby. That is, I wanted to write this:

class Array
  def powerset
    self.filterM {|x| [true, false]}
  end
end

First thing I need is a list monad:

class Array
  def self.unit(x)
    [x]
  end

  def bind(&f)
    self.inject([]) do |acc, e|
      acc + f.call(e)
    end
  end
end

I quickly hit my weekly reminder that Ruby does not have Array#rest, so I added that:

class Array
  def rest
    r = self[1..-1]
    r.nil? ? [] : r
  end
end

Whew; now things are easier. Next I needed filterM, so I added it to Enumerable as a faithful copy from Haskell (expanding the do notation into the >>= notation):

module Enumerable
  def filterM(&p)
    return self.class.unit([]) if self.empty?
    p.call(self.first).bind do |flg|
      self.rest.filterM(&p).bind do |ys|
        self.class.unit(flg ? ([self.first] + ys) : ys)
      end
    end
  end
end

Now my original Array#powerset method works:

irb(main):013:0> [1,2,3].powerset
=> [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

I expect you to write that quickly in your next interview.

About these ads

3 Comments

  1. Posted February 5, 2011 at 5:19 pm | Permalink

    I found this earlier today and thought it was interesting. I had to come up with an implementation of the powerset in class this week, and once I completed my version I wanted to know what other people were doing as well. Unfortunately, I ran yours with (1..20).to_a.powerset a few minutes ago and still have not managed to produce a result, so yes, this is a little slower than what you’d want to answer the question, but I love the use of Haskell’s methodology to solve the problem.

    In any case, I don’t know if you’re interested, but I the solution that I managed to come up with (before looking anything up) was:


    class Array
    def powerset
    if block_given?
    if self.length == 0
    yield []
    else
    self[0..-2].powerset do |set|
    yield set
    yield set + [self[-1]]
    end
    end
    self
    else
    Enumerator.new { |sets|
    self.powerset do |set|
    sets << set
    end
    }
    end
    end
    end

    I know that you posted this forever ago, but like I said, I thought it was an interesting solution to the problem.

    • Posted February 5, 2011 at 5:21 pm | Permalink

      Ugh, that looked awful, let’s try that with pre tags instead. >.>

      class Array
        def powerset
          if block_given?
            if self.length == 0
              yield []
            else
              self[0..-2].powerset do |set|
                yield set
                yield set + [self[-1]]
              end
            end
            self
          else
            Enumerator.new { |sets|
              self.powerset do |set|
                sets << set
              end
            }
          end
        end
      end
      
      • Posted February 5, 2011 at 8:17 pm | Permalink

        Neat, thanks Andrew!

        The Haskell-in-Ruby implementation is definitely slower but it was a fun puzzle and could maybe even help people understand the list monad more.


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: