当前位置: 动力学知识库 > 问答 > 编程问答 >

Haskell - scanning over multiple lists at once

问题描述:

Doing some university homework I found myself doing something similar to:

scanl' (\acc (a, b, c) -> expression) 0 $ zip3 as bs cs

With different numbers of zipped lists, up to 7. This seems pretty inefficient since it constructs an auxiliary list of tuples.

It isn't very hard to define scanl2, scanl3, etc recursively and avoid constructing an extra list, but the amount of boilerplate required is ridiculous.

Is there a way to have both - lack of boilerplate and low memory usage ?

网友答案:

As mentioned in the comments, a Haskell program that looks like it's generating an "extra list" rarely actually generates the extra list (thanks to lazy evaluation, among other things), so there is unlikely to be additional memory usage introduced by the use of zip3. If the function is used in such a way that the list can be consumed as it is produced, no actual lists (intermediate or final) will be produced whatsoever.

For example, consider the following Scan.hs program which consumes a large list with sum as it is produced:

import Data.List (scanl')

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc]
scanl3 f z as bs cs = scanl' f z $ zip3 as bs cs

main = print $ sum $ scanl3 (\z (a, b, c) -> z + a*b + 2*c) 
                            0 [1..100000000] [10,20..] [100,200..]

If you compile this for profiling with -O2 optimizations:

ghc -prof -rtsopts=all -O2 Scan.hs 

then run it with heap profiling:

./Scan +RTS -h
hp2ps Scan.hp
evince Scan.ps

you'll find that it runs in constant memory about 35k), creating neither the intermediate zip3 list nor the final scanl3 list explicitly.

If scanl3 is used in a context where the entire list needs to be held in memory at once, the intermediate list still shouldn't cause any increased memory use, though the only way to be sure would be to profile both it and an alternative implementation in a specific usage case.

With respect to time overhead of using zip3 as an intermediate step, again you really need to benchmark against an alternative implementation to be sure. I compared the above version using zip3 against a recursive version:

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc]
scanl3 f z (a:as) (b:bs) (c:cs) = z : scanl3 f (f z (a, b, c)) as bs cs
scanl3 _ z _ _ _ = [z]

using the same test case as above compiled with -O2 and found the runtime to be nearly identical (15.2sec for zip3 versus 16.8sec for recursive).

Note that I didn't explicitly make my recursive version strict, but in the particular usage case (summing it as it was produced), that doesn't make any difference.

Edit: Actually, I guess it does make a difference. A strict version using a bang pattern:

{-# LANGUAGE BangPatterns #-}

scanl3 :: (acc -> (a, b, c) -> acc) -> acc -> [a] -> [b] -> [c] -> [acc]
scanl3 f !z (a:as) (b:bs) (c:cs) = z : scanl3 f (f z (a, b, c)) as bs cs
scanl3 _ z _ _ _ = [z]

looks like it might run consistently 0.5-1.0 secs faster (out of 16secs).

分享给朋友:
您可能感兴趣的文章:
随机阅读: