Re: [Haskell-cafe] what does @ mean?.....

On Fri, 2007-12-28 at 09:51 -0700, Luke Palmer wrote:

On Dec 28, 2007 9:35 AM, Jules Bean wrote:

...

In particular, adding sharing can stop something being GCed, which can convert an algorithm which runs in linear time and constant space to one which runs in linear space (and therefore, perhaps, quadratic time).

I've heard of this before, but can you give an example?

I don't know why they were so modest. Run the following two programs in the Haskell implementation of your choice 1) powerset [] = [[]] powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) 2) powerset [] = [[]] powerset (x:xs) = xss ++ map (x:) xss where xss = powerset xs Compare it on programs such as length (powerset [1..n]) for n in the range of 20-30. Make sure you aren't doing anything important when you use the second version for larger inputs. These two programs are an extreme case of trading space for time, and an extreme case of why common subexpression elimination can be a massive pessimization. In this particular case, there is an exponential increase in the size of the live-set.