Scala Hacking: Computing Powerset

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)
}
view raw powerset.scala hosted with ❤ by GitHub

Isn’t this approach quite concise and elegant? 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 a 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(""))
view raw powerset.fs hosted with ❤ by GitHub

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s