[Haskell-cafe] Space usage and CSE in Haskell

[Dan Weston]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>