Maybe it behooves writers of GHC libraries who create list generating functions f where the complexity of length . f is strictly less than the complexity of f itself to provide an fLength function and a rewrite rule for it: {-# RULES "listLength" length . f = fLength #-} Then people like me could mindlessly write
main = print (length (power_list [1..20]))
and get
main = print (power_list_length [1..20])
without worrying about efficiency. Dan ok wrote:
On 25 Jul 2007, at 6:50 pm, Melissa O'Neill wrote: [section 23.4.2 of Simon's 1987 book].
The really scary thing about this example is that so much depends on the order in which the subsets are returned, which in many cases does not matter. Here's code that I tried with GHC on a 500MHz SPARC.
With today's memory we might be willing to put up with the O(2**N) space cost (as long as N isn't too big), because that saves us more than a factor of 3 in time. But changing the order of the results gives us a nice bounded space solution which is nearly 9 times faster than the naive sharing code.
In a non-trivial program, we wouldn't have a hope of spotting issues like this without memory use profiling. Unless someone has some ideas about how to design code so that it's not a problem?
main = print (length (power_list [1..20]))
power_list :: [Int] -> [[Int]]
power_list [] = [[]] {- Classic 23.4.2 first definition of power_list with space sharing and therefore "O(2**N) transient residency".
power_list (x:xs) = pxs ++ map (x :) pxs where pxs = power_list xs
-- 3.540 user + 0.220 system = 3.760 total seconds. -}
{- Classic 23.4.2 second definition, with recomputing, "constant residency", but poor run-time.
power_list (x:xs) = power_list xs ++ map (x :) (power_list xs)
-- 12.130 user + 0.110 system = 12.240 total seconds. -}
{- A fairly obvious variant of the first definition. The order is changed to eliminate wasted appends, but the space behaviour doesn't change that much.
power_list (x:xs) = map (x :) pxs ++ pxs where pxs = power_list xs
-- 2.020 user + 0.240 system = 2.260 total seconds. -}
{- Another change to the order to give us MORE sharing takes less time AND less space. The surprise is how much less time. -} power_list (x:xs) = foo (power_list xs) x where foo [] _ = [] foo (y:ys) x = (x:y) : y : foo ys x
-- 0.370 user + 0.060 system = 0.430 total seconds.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe