powerset

[Graham Klyne]

At 19:50 04/06/03 -0400, Derek Elkins wrote:
> > >     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.

Thank you.  I stand duly instructed... this commentary was the kind of 
feedback I was hoping to draw, though I did not mean to cause so much 
anguish :-)

> > You can also write
> > [1..length as] rather than use the intRange function, which looks
> > prettier. :-)

I agree with Liyang that [1..  ] is much prettier.  That's one idiom I've 
yet to absorb.

(I came to functional programming thinking that it was fundamentally 
simpler than conventional languages -- none of those complicated control 
structures to worry about, just expressions -- but the syntactic richness 
of Haskell seems to be quite beyond the conventional languages that I have 
used.)

>Indeed, I think I've used length all of 3 times.

This is an interesting comment.  I've found myself using length quite 
often, even when it feels not-quite-right to me.  Maybe it's that I'm not 
yet used to designing algorithms functional-style, or alternative idioms 
that I'm overlooking.  I'm not sure what I'm missing here, so this is a 
vague probe for further insight.

>   You (Graham) also have
>some parentheses issues; e.g. in foo ++ (combinations 5 l) the
>parentheses are superfluous.

I'm tempted to argue that being superfluous doesn't mean they shouldn't be 
there.  This isn't just a functional programming issue... I find that when 
there are many levels of operator precedence it's easier to be explicit 
than to try and remember what they all are -- as much for reading the code 
as writing it in the first place.  But maybe I'm still reading functional 
code in the wrong way?  (I still scratch my head over some of the 
prelude/library functions, though it's getting easier.)

>(++) 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.

I'd just about figured the ShowS idea, but I've yet to get a handle on this 
idea of [a] 'monoid'.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E