[Haskell-cafe] appending an element to a list

[Evan Laforge]

> Lets look at the actual reductions going on. To make the example easier,
> I would like to use last instead of your complicated until. It shouldn't
> make a difference.

[ winds up doing twice as much work ]

This was also my intuition.  I had a function that built up a large
output list by generating chunks and ++ them onto the output (e.g.
basically concatMap).  My intuition was that this would get gradually
slower because each (++) implied a copy of the previous part of the
list.  So if I have another function consuming the eventual output it
will get slower and slower because demanding an element will reduce
the (++)s for each chunk, and copy the element 1000 times if I have
appended 1000 chunks by now.

So I switched to using DList, which has O(1) append.  Then I ran
timing on a list that wound up adding up a million or so chunks... and
both versions were exactly the same speed (and -O2 gave both an
equally big speed boost).

In fact, when I try with a toy example, the DList using one is much
slower than the concatMap using one, which I don't quite understand.
Shouldn't concatMap be quite inefficient?

The program below gives me this output:

15000000
45.7416
15000000
110.2112

-O2 brings both implementations to 45.

Interestingly, if I call 't1' from ghci, it sucks up 1gb of memory and
slows the system to a crawl until I kill it.. this is *after* it's
computed a result and given me my prompt back... even if its somehow
keeping the whole list around in some ghci variable (where?), isn't
1gb+ a lot even for 15m boxed Integers?  And why does it continue to
grow after the function has completed?  The compiled version doesn't
have this problem.


import System.CPUTime
import qualified Data.DList as DList

dconcat_map f xs = DList.toList (DList.concat (map (DList.fromList . f) xs))

mkchunk n = [n, n*2, n*3]

main = do
    t1
    t2

t1 = do
    let a = concatMap mkchunk [0..5000000]
    t <- getCPUTime
    print (last a)
    t2 <- getCPUTime
    print (fromIntegral (t2 - t) / fromIntegral cpuTimePrecision)

t2 = do
    let a = dconcat_map mkchunk [0..5000000]
    t <- getCPUTime
    print (last a)
    t2 <- getCPUTime
    print (fromIntegral (t2 - t) / fromIntegral cpuTimePrecision)