powerset

[Liyang HU]

Hi Graham,

On Wed, Jun 04, 2003 at 12:08:38PM +0100, Graham Klyne wrote:
> I thought this may be a useful exercise to see how well I'm picking up on 
> functional programming idioms, so I offer the following for comment:

>     foldl (++) [] [ combinations n as | n <- intRange 1 (length as) ]

By your use of the `intRange' function, I get the feeling you're still
thinking somewhat imperatively. (It's awfully reminiscent of a for-loop...)
Were you trying to write the function from some definition? (The set of all
subsets of X with size <= |X| et c. You're looping over the size of the
subset, per se...?)

(Side note: I can think of few instances where you _need_ to deal with the
length of a list directly -- more often than not you can (and probably
should) let recursion take care of that. You can also write [1..length as]
rather than use the intRange function, which looks prettier. :-)

A key point is to try and think of how you can relate one case of the
problem to a simpler instance of the same problem, rather than tackling it
head on. Start by looking at the power set of a few small examples. The
power set of the empty set is the size 1 set consisting of the empty set:

> pset [] = [ [] ]

and a couple more:

> pset [a] = [ [a], [] ]
> pset [b, a] = [ [b, a], [b], [a], [] ]

Notice how the `second half' of pset [b, a] is exactly pset [a]. Can you see
anything that would relate the sets [b, a], [b] to [a], []? (Yes! Chop off
the leading b! :) Let's try to generalise this:

Take a set X, and an element y not in X. Denoting the power set function by
P(), I hope you can see that P(X u {y}) certainly contains P(X). But no set
in (read: member of) P(X) has y as a member, and funnily enough, if we add y
to each element of P(X) we get missing bits of P(X u {y}).

(The fact that the size of the power set is 2^|X| should serve as a hint --
you want to double the size of your power set for each element in X.) So we
arrive at our solution:

> pset [] = [ [] ]
> pset (x:xs) = let ps = pset xs in map (x:) ps ++ ps

Or at least, this is what would be going through my head if I were trying to
write this. ^_^ Hope it helps a bit...

later,
/Liyang
-- 
.--| Liyang HU |--| http://nerv.cx/ |--| Caius@Cam |--| ICQ: 39391385 |--.
| :::::::::::::::::::::: This is not a signature. :::::::::::::::::::::: |