On Wed, 4 Jun 2003 15:08:44 +0100
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) ]
*cries out in pain and horror* fold_l_ (++) over combinatorially large lists! (++) has gotten a reputation for being slow. (++) isn't slow in and of itself, even using it a lot isn't slow, what -is- slow is using it left associatively. What happens then is that (a++b)++c builds a copy of a then tacks on b, then it builds a copy of a++b and tacks on c. In this case we've copied a twice when we should have only copied it once. Obviously for ((a++b)++c)++d it'll be copied three times and b twice and so forth. To add insult to injury, there is already a standard function that does what you want, concat, which is defined as foldr (++) [] in the report. In fact, you could rewrite the whole thing as concatMap (flip combinations as) [1..length as]. A list comprehension with only one source and no filters is the same as a map.
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. :-)
Indeed, I think I've used length all of 3 times. You (Graham) also have some parentheses issues; e.g. in foo ++ (combinations 5 l) the parentheses are superfluous. (++) is slow though in that seemingly innocent uses can become n^2. A simple example is displaying a binary tree. A tree like /\ /\ will cause left associative uses of (++). Hence the prelude type ShowS = String -> String and shows :: Show a => a -> ShowS. The problem is we don't want left associativity, so what we do is make a context that says do everything else to the right, then this, e.g. "Foo"++everythingelse. This is simple enough to do with ("Foo"++). (As a side note, using the Writer/Output monad with the list/string monoid is probably not the best of ideas, instead you can use the function monoid and tell ("foo"++).) You can see that this technique is more or less just adding an accumulating parameter as you'll have to provide the 'initial' value.