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. :::::::::::::::::::::: |