[Haskell-cafe] Powerset of a set

Olaf Klinke olf at aatal-apotheke.de
Tue Sep 15 13:02:48 UTC 2015


This was one of the most woundrous moments I ever had with reading a Haskell library: If lists are used to represent finite sets (hence disregarding order and multiplicity of elements), then 

Control.Monad.filterM (const [False,True]) :: [a] -> [[a]]

computes the powerset. Exercise for Jorge: Read the source code of filterM [*], understand what this function is doing, and why this indeed computes (a representation of) the powerset. 

Cheers,
Olaf

[*] http://hackage.haskell.org/package/base-4.8.1.0/docs/src/Control.Monad.html#filterM


More information about the Haskell-Cafe mailing list