[Haskell-cafe] Powerset of a set

[Jerzy Karczmarczuk]

Olaf Klinke :
> 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.
This is very nice and compact. But Olaf begins with:
"This was one of the most woundrous moments I ever had with reading a 
Haskell library"

For me it became once a source of pain... After having taught Haskell 
for some years, I fell into the overgeneralization trap, trying to 
convince students that the most generic procedures are Good. Final calls 
are compact, boilerplate reduced, the patterns used may be inspiring and 
reused, etc.

But for the beginners, needing a clue on how a - say - non-deterministic 
algorithm works, it was a failure. It *could* work, if the students had 
time and patience to concentrate on those universalities.
No, an advice: "read the library sources" is for people who have really 
some free time, or want to specialize. Never for beginners, whose first 
aim is to solve THE problem.

Finally, I began with a crash course of Prolog, with the generation of 
ANY subset: either you choose an element or not, and that's all.

sset([],[]).
sset([X|Q],R):-(R=T;R=[X|T]),sset(Q,T).

and we reconstructed the List Monad from it. And it worked, although it 
was not so ambitious. Here it is, if somebody doesn't want it, don't 
read. But no comprehensions inside, so, the needs of Jorge M. are not 
satisfied.

sset [] = return []
sset (x:q) =
  do
   t <- sset q; return t ++ return (x:t)

((( or
sset (x:q) = sset q >>= (\t -> return t ++ return (x:t))
)))

This is not very ambitious, quite plain (and not optimized). But an 
ambitious beginner should be able to understand what is going on ; no 
"(const [False,True])" inside, which is obviously artificial.
We tried to concentrate on the immediate solution, and only after 
treating permutations, partitions of an integer, and several other 
examples, we could generalize...

Jerzy