This post is an attempt to understand how the execution for the calculation of a PowerSet is done for a given list of input. Note that I said calculation, since this is a set calculation technically. The idea comes from this link. The Haskell code tries to mirror the algorithm given in the Wiki.
The basic idea of the algorithm is this – take one element from the set and concatenate (perform union in Mathematical terms) this element with the powerset of the remaining elements. And to calculate the powerset of the remaining elements, continue the same process recursively. And the powerset of an empty list [] is a list with an empty element [[]], which is the terminating condition for the recursion. The Haskell code on the site is simple looking, but packs a good punch. map in Haskell is like map in any other language – it applies the function given to every element in the list. In the code below the (x:) means concatenate x in the beginning. And the ++ operator is to add an element to the end of a list
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
Let us walk through the execution of the recursive algorithm. For the sake of brevity, I am going to name the function ps
ps [1,2,3] = ps [2,3] ++ map (1:) (ps [2,3])
^
|--- (1)
ps [2,3] = ps [3] ++ map (2:) (ps [3])
^
|-- (2)
ps [3] = ps [] ++ map (3:) (ps [])
^
|-- (3)
= [[]] ++ map (3:) (ps [])
^
|--(4)
= [[]] ++ map (3:) ([[]])
^
|--- (5)
= [[]] ++ [[3]]
= [[],[3]]
--- so, the result of (2) is ps [3] = [[],[3]] -- (Result1)
Now we come back to the ps[2,3]. So,
ps [2,3] = [[],[3]] ++ map (2:) (ps [3])
=> ps [2,3] = [[],[3]] ++ map (2:) ([],[3]) -- from Result1
=> ps [2,3] = [[],[3]] ++ [[2],[2,3]]
=> ps [2,3] = [[],[3],[2],[2,3]] -- (Result2)
Now we come back to ps [1,2,3]
As noted above,
ps [1,2,3] = ps [2,3] ++ map (1:) (ps [2,3])
=> ps [1,2,3] = [[],[3],[2],[2,3]] ++ map (1:) (ps [2,3])
-- from (Result2) we know ps[2,3]
=> ps[1,2,3]=[[],[3],[2],[2,3]] ++ map (1:) ([],[3],[2],[2,3])
=> ps[1,2,3]=[[],[3],[2],[2,3]] ++ [[1],[1,3],[1,2],[1,2,3]
=> ps[1,2,3]=[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
I have reused the results mentioned in Result1 and Result2, but during execution, those results are re-computed ( I am not 100% sure on this, since there is a possibility of partial evaluation and storing the results of the partial evaluation in Haskell)
. This sense of disbelief / wonder (and it works both ways) mostly comes because the reader can’t vouch for the veracity of the numbers. The assumption always is that the person talking about the numbers (or the statistic, technically speaking) knows what (s)he is talking about. And even if that is not the case, it is very easy to be lost amongst the numbers – when there are averages, percentages, YoY (year-on-year) growth, percentage points, APRs and myriad other measures that are used to make the person talking about these (who more often than not is selling something) seem either very good or very bad. And looks like all these people seem to have the same field manual – 
. For example, in the chapter 13, the author tries to explain the complex plane and how the function’s graph looks (knowing how a function’s graph looks definitely provides a lot of insight into how the function behaves), but I couldn’t really grasp it very well. And further in the chapter 20, he talks about Reimann operators and other approaches, which was too complex for my rather limited mathematical knowledge (no pun intended). For me, the section 2 is something that I will have to re-read till I get my head around it. For people who have a better grounding in mathematics than I do, I guess it will be easier