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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
