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.
