powerset

[Derek Elkins]

On Wed, 4 Jun 2003 15:08:44 +0100
Liyang HU <liyang@nerv.cx> wrote:

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