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.

### Like this:

Like Loading...

*Related*

## 3 Comments

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.

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

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.