[Haskell-cafe] Powerset of a set
Jerzy Karczmarczuk
jerzy.karczmarczuk at unicaen.fr
Tue Sep 15 18:02:03 UTC 2015
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
More information about the Haskell-Cafe
mailing list