# A declarative way to calculate power sets in JavaScript (with a short detour to Haskell)

There is a definite differentiation between declarative and imperative ways of programming. The latter used to be explained as the method when you answer the question: “What are the steps/changes to do sequentially?”, while the former method answers “What is needed?” or even: “How can the solution be derived from the problem, or a solution for a smaller sub-problem?”

One form of being declarative is recursion. Recursion happens when — in an imperative wording — a function *calls* itself in its *body*, or — in a declarative wording — when a function *refers* to itself.

**The power set problem as an example**

A power set of a set is a set that contains each and every subset of it, including the empty set and the actual set itself.

The power set of the empty set is the empty set.

For example the power set of {x} is: {{}, {x}}

And the power set of {x, y} is {{}, {x}, {y}, {x, y}}

**Imperative approach**

An imperative way to write an algorithm could be to start with a set containing the empty set as the initial candidate result set of subsets, and then iterating through each of the elements of the input set and “populate” this candidate result set by “cloning” every subset in it with a version that has the actual input element being iterated upon as an addition:

- given an
*inputSet*of elements to calculate the power set of - let
*resultSetOfSubsets*be the set that contains only the empty set: {{}} - for each
*inputElement*in the*inputSet*do the following: - for each
*subset*in the*resultSetOfSubsets*do the following (**∪**= union of sets): - add the subset:
*subset**∪**{ inputElement }*to*resultSetOfSubsets*

**Implementation in Javascript**

`const powerSet = (inputSet) => {`

let resultSetOfSubsets = [[]];

for (let x = 0; x < inputSet.length; x++) {

let subSetsToAdd = [];

for (let y = 0; y < resultSetOfSubsets.length; y++) {

subSetsToAdd.push(resultSetOfSubsets[y].concat(inputSet[x]));

}

resultSetOfSubsets = resultSetOfSubsets.concat(subSetsToAdd);

}

return resultSetOfSubsets;

};

It’s not a huge amount of code, it’s not that difficult to understand, but not that clear either and an other disadvantage of imperative approach has already appeared too:

The “let subSetsToAdd = [];” is there only to tackle the problem that if we didn’t have that temporary array but added the new subset right into *resultSetOfSubsets *then we would mutate the list being actively iterated upon which would definitely lead to problems. Using *forEach *would help but solely because of the fortunate way in which it was implemented. It would be still somewhat spooky, though, if correctness depended on such things.

The imperative way of describing things often lead to unnecessary introduction of the concept of “time” and the importance of an arbitrary order in which the mutations happen to data.

**Declarative approach**

We can make an observation. The power set of any non-empty set can be generated recursively by:

- taking one element out, getting a set with a size decreased by 1
- generating the power set of the remaining set
- make a clone of every set from the above generated power set which has additionally has the element taken out in the first step to every copy

So for example the power set of {x, y} is generated like this:

- take one element out,
*head*=x - the remaining set is {y}, and the power set of it is: { {}, {y} }
- make a copy of all of the elements of the power set which has the element
*head*added ( {} => {} + {x}, {y} => {y} + {x, y})

And we correctly get that the power set of {x,y} is { {}, {x}, {y}, {x, y} }

Important to note that this not a completely different solution, it has the same structure as the one above in the imperative approach, but now it is turned “upside-down”. Instead of defining *what it takes* to build everything from ground up, we defined how the power set of a set *depends on* the power set of a smaller set.

**Implementation in Haskell**

Now let’s use the power of Haskell’s declarative syntax and a form of monadic composition to get to a very concise and clear notation:

`powerset :: [a] -> [[a]]`

powerset [] = [[]]

powerset (head:tail) =

powerset tail >>= (\subsets -> [subsets, head:subsets])

The first line says that *powerset* will be a function that turns a list of elements of any type into a list of lists of the same type.

The second line is the base case for the empty set.

The third line has the 3 step core which has been described above:

With the ‘(head:tail)’ pattern matching we take out the head element, then with ‘powerset tail’ we get the powerset of the rest, and then the *>>= *operator stands for the monadic *flatmap *or *bind *operation in Haskell. (This is really good writing in the topic) For simplicity’s sake we can think of it as a regular *map* function that transforms one subset into a list of two subsets (one that has the *head *attached, and another one that is the same as the input) directly followed by a *flat* transformation to avoid the unnecessary nesting.

**Conversion to JavaScript**

It turns out that JavaScript also has capabilities to reach almost the same level of conciseness. We can utilize the ternary operator as a “pattern match”, the … array de-structuring operator, and recently there is even a *flatmap *already implemented natively on arrays but a *map *+ *flat *combination would also have the same effect:

`const powerset = ([head, ...tail]) => `

(

head == null ? [[]] :

powerset(tail).flatMap(subsets =>

[subsets, subsets.concat(head)])

);

**Conclusion**

Declarative approach and recursion many times can result in much smaller, cleaner and tighter code in a way that it leaves less room for bugs to sneak in.

Considering higher-level functional approaches can often pay out really well even in situations and languages not exactly optimal for implementation of these, as it can be seen from the above example. It is the mindset that matters most not the tool set.

With recursion there is an additional thing to keep in mind, though. For larger problems and in most of the languages it can make the stack blow up. Fortunately this problem can be solved by using for example tail recursion, or trampolining.