Re: inits

Nils Anders Danielsson wrote:

On Mon, 10 Apr 2006, Chris Kuklewicz wrote:

...

If the goal is speed, then this definition is running over 10% faster with ghc -O2 on my powerbook for (sum $ map length $ inits [1..10000])

inits' = helper id where helper f [] = (f []):[] helper f (x:xs) = (f []):helper (f.(x:)) xs

This function looks like it's exactly equivalent to the H98 one, but I haven't checked the details.

The Haskell 98 Report http://www.haskell.org/onlinereport/list.html gives:

-- inits xs returns the list of initial segments of xs, shortest first. -- e.g., inits "abc" == ["","a","ab","abc"] inits :: [a] -> [[a]] inits [] = [[]] inits (x:xs) = [[]] ++ map (x:) (inits xs)

Which, using ghc-6.4.2 -O2, runs the benchmark operation that I am using (sum $ map length $ inits [1..10000]) in 50.9 seconds. (Just as fast as GHC's Data.List.init, so I expect that GHC uses the code in the report). The actual timing output:

pamac-cek10:/tmp chrisk$ time ./i6 50005000

real 0m56.197s user 0m49.856s sys 0m1.003s

The helper code runs in 5.2 seconds:

pamac-cek10:/tmp chrisk$ time ./i2 50005000

real 0m5.750s user 0m5.114s sys 0m0.111s

Running with +RTS -sstderr -RTS shows the code in the report is allocating exactly 4 times as much space on the heaps. The speed does not change if I use main = print $ sum $ map length $ inits2 (take 10000 [True,True ..])

Furthermore, this definition made me think of a flaw in many of the others: they won't work for infinite lists. (Note that length ([1..] :: [Int]) = maxBound :: Int.)

Subtle problem. But [1..] defaults to Integer which is "infinite" enough. The original example will need to use genericTake . . .