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.