Gist: Computing Powerset with Scala

Given a set represented as a String, we can compute its powerset using foldLeft, as shown below.

def powerset(s: String) = 
    s.foldLeft(Set("")) { 
        case (acc, x) => acc ++  acc.map(_ + x)
    }

The following snippet shows a pretty-printed output from powerset for a set: "abc".

scala> powerset("abc").toList sortWith ( _ < _) mkString "\n"
res3: String = "
| a
| ab
| abc
| ac
| b
| bc
| c"

Following is an F# implementation of this same function.

let powerset (s:string): Set<string> = 
  s.ToCharArray() 
  |> Array.fold(
      fun (acc: Set<string>) x -> acc + (Set.map(fun y -> x.ToString()+y) acc)
      ) (Set.empty.Add(""))