Discussion on: Build a PowerSet

[Carsten]

Maybe it's enlightening to see a functional take on that as well.
If you think a bit about this, producing all members of a powerset basically comes down to go over all elements of the input-set.

For every such you have the choice of including it in a subset or not (so you can directly see that there will be 2ⁿ subsets for a set of size n)

This idea directly translates into this (yeah sorry it's Haskell):

powerset []     = [ [] ]
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

meaning:

• if you've got the empty set (really a list here but hey FP right?) the only subset of this is the empty-subset itself

• or else you have a set with at least one element x (and possible more elements xs)

  • now you have two classes ob subsets: one where x is included, and one where it is not
  • you get both by recursively getting all the subsets of the remaining elements xs - just include x everywhere in one copy (that's the map (x:) part - ++ just concatenates the two sets ob subsets

call me weird but I consider that easier to read and reason about than the imperative Java solution ;)

[Tomer Ben David]

This is definitely beautiful! :)

This is what I like about declarative and functional code :)

It's pure :)

I have to add that I have a place also for imperative code, what I do like about imperative code is that instead of repeating the definition (which is not a bad thing it's beautiful), I'm actually taking the mini steps and it makes me understand what's happening better. (that's at least how I understand things).

In addition, let's say I to log something out to the logger, I'm not sure what would happen to the functional code, or I would need to send some metrics to monitoring, I'm sure there is a functional solution to it (monad and friends) but this is where things get's heavy on me.

[Carsten]

depends on what you want to log I guess (seems doubtful, that you want to log anything here - indeed I never had the need to log anything inside a pure function as you can test it anytime if you know the input to it)

but sure most of us learned programming in the more operational/imperative mindset (basically by doing step-by-step debugging in our head) so it might take some time to get "warm" with FP ;)

But in those more mathematical problems (where the problem often is recursive in nature) it's just a natural fit ;)

[Tomer Ben David]

cool, adding the scala functional :: recursive :: declarative :: concise way to the post :)) .

  def powerSet(set: Set[Int]): Set[Set[Int]] = {

    set.toList match {
      case Nil => Set(Set.empty[Int])
      case x :: xs => powerSet(xs.toSet).map(xsi => xsi + x) ++ powerSet(xs.toSet)
    }
  }

  println(powerSet(Set(1,2,3))) // Set(Set(), Set(3, 1), Set(2), Set(2, 1), Set(3, 2), Set(3), Set(3, 2, 1), Set(1))

[Tobias Salzmann]

I remember this firmly as one of the more difficult exercises in my introductory programming course at university. But finding that solution was so rewarding!