Lack of laziness in some vector operation

Question

This code is trying to look forward to [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 assembly, unoptimised first create two vectors created using fromList . Since vectors are strict (and non-aligned hyperstrings), this will not work, since you cannot build a vector of infinite size.

If you compile -O2 , stream fusion comes into play. Now all intermediate vectors (those fromList ) are not created at all. Since zipWith stops after completing the first data feed, you now have a completion function.

But in general: do not use endless deliveries with vector operations, the semantics of your functions now depend on your level of optimization, which is bad.

The original streaming fusion paper describes the transition from lists to streams and back to lists again. For simplicity, you can think of lists as vectors (since vectors add a bunch of additional material, such as memory allocation, monadic behavior, etc.).

In general (and much simplified), rewrite rules are used for the internal representation of vectors as streams, which allows merging, and streams are then returned to vectors.

Answer 2

Data.Vector.fromList is documented to take O (N) time. Here you have provided an infinite number of elements, so it takes an infinite amount of time to complete.

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