No laziness in some vector operation

Question

This code tries to eagerly evaluate [1..] which causes an infinite loop.

import qualified Data.Vector as V

infiniteLoop = V.zipWith (+) (V.fromList [1..4]) (V.fromList [1..])

Why is this so?

Answer 1

Compile with -O2.

... ok this only works in certain cases.

In your unoptimised build, the two vectors created via fromList are built first. Since vectors are spine-strict (and unboxed ones hyperstrict), this will fail as you can not construct an infinite-size vector.

If you compile with -O2, stream fusion comes into play. Now, all intermediate vectors (the ones from fromList) are not created at all. Since zipWith stops once the first supply of data is done, you now have a terminating function.

But in general: don't use infinite-size supplies with vector operations, the semantics of your functions now depend on your optimization level, which is bad.

The original "stream fusion" paper describes the switch from lists to streams, and back to lists again. For simplification you can think of lists as vectors (as vectors add a bunch of additional stuff like memory allocation, monadic behaviour, ...).

In general (and much simplified), rewriting rules are used to internally represent vectors as streams, enabling fusion, and streams are then turned back into vectors.

Answer 2

Data.Vector.fromList is documented to take O(N) time. Here, you've supplied an infinite number of items, so it takes infinite time to complete.

As for why vectors can't be constructed lazily: they promise good performance for other operations (take, drop, length, indexing...), which requires using a data structure that knows how many elements exist.