A declarative way to calculate power sets in JavaScript (with a short detour to Haskell)Zoltán TamásiBlockedUnblockFollowFollowingApr 19There 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 exampleA 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 approachAn 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 oflet 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 resultSetOfSubsetsImplementation in Javascriptconst 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 approachWe 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 1generating the power set of the remaining setmake 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 copySo for example the power set of {x, y} is generated like this:take one element out, head=xthe 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 HaskellNow 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 JavaScriptIt 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)]) );ConclusionDeclarative 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.
.