A demo powerset function implemented in Haskell and Python.

powerset-in-haskell-and-python.org

Here’re two powerset function implemented in Python and Haskell.

import copy

def powerset(s):
    if s == []:
        return [[]]
    elif len(s) == 1:
        return [[], s]
    else:
        powerset1 = powerset(s[1:])
        powerset2 = []
        for ss in powerset1:
            new_ss = copy.deepcopy(ss)
            new_ss.insert(0, s[0])
            powerset2.append(new_ss)

        return powerset1 + powerset2

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset [x] = [[], [x]]
powerset (x:xs) = [x:px | px <- powerset(xs)] ++ powerset(xs)

And we can see that in a language with Pattern matching, Lazy evaluation and immutable data structures like Haskell, it’s really easy and elegant to implement some mathematical functions.