Calculate powerset of a set

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)