[Haskell-cafe] Re: Euler 201 performance mystery

[apfelmus]

apfelmus wrote:
> In other words, we have now calculated the more efficient program
> 
>   euler201 = map snd . filter ((==50) . fst) . subsums $ squares
>      where
>      subsums []     = singleton (0,0)
>      subsums (x:xs) = map (\(n,s) -> (n+1,s+x)) (subsums xs) `union` subsums xs

I forgot something very important, namely that the common subexpression 
subsums xs  has to be shared

   euler201 = map snd . filter ((==50) . fst) . subsums $ squares
      where
      subsums []     = singleton (0,0)
      subsums (x:xs) = let s = subsums xs in map (\(n,s) -> (n+1,s+x)) s `union`s

Otherwise, this exercise would be pointless and the runtime exponential ... :O


Regards,
apfelmus