在某些向量操作中不需要懶惰

此代碼嘗試熱切評估導致無限循環的[1..]。在某些向量操作中不需要懶惰

import qualified Data.Vector as V 

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

這是爲什麼？

來源

2014-07-05 Evan Sebastian

一個向量需要知道它的大小。與列表不同的是，隨着數據傳入，矢量不能逐漸建立和增長。我不確定Monad是如何進入這裏的。 –

你應該讓這個答案@n.m。 – Carsten

@ n.m。矢量是一個流，它似乎擁有一個Monadic值。追蹤'Data.Vector.fromList'的源代碼將引導你從模塊['Data.Vector.Fusion.Stream.Monadic']（http://hackage.haskell.org/package/ vector-0.4/docs/src/Data-Vector-Fusion-Stream-Monadic.html＃fromList） –

編譯-O2。

...好吧，這隻適用於某些情況。

在您的unoptimised構建中，首先構建通過fromList創建的兩個向量。由於矢量是嚴格的脊柱（和非盒式超弦），這將失敗，因爲你不能構造一個無限大小的矢量。

如果使用-O2進行編譯，則stream fusion進入編輯狀態。現在，所有中間向量（來自fromList的那些向量）都不會被創建。由於zipWith一旦第一次提供數據就停止，您現在具有終止功能。

但一般情況下：不要使用矢量操作的無限大小的供應，您的函數的語義現在取決於您的優化級別，這是不好的。

原來的"stream fusion" paper描述了從列表切換到流再次返回列表。爲了簡化，您可以將列表視爲向量（因爲向量會添加一些額外的內容，如內存分配，單點行爲...）。

在一般情況下（並且非常簡化），重寫規則用於在內部將向量表示爲流，從而實現融合，然後將流轉換回向量。

來源

2014-07-05 11:51:22 choener

這是（也許不幸）是正確的答案。在這種特殊情況下，流式融合「Vector」使用能夠擺脫無限列表。但是有兩個警告。一，你必須編譯優化，以發生流融合。二，它是脆弱的，在這種融合中，有時甚至不會觸發優化。正如@choener所說，你不應該讓程序的語義依賴於優化工作。 – Carl

我相信矢量包更直接地在不同的模塊中公開流處理機器。 – dfeuer

Data.Vector.fromList是documented需要O（N）時間。在這裏，你提供了無數的項目，所以需要無限的時間才能完成。至於爲什麼不能構建懶惰的載體：它們承諾對其他操作（採取，拖放，長度，索引......）具有良好的性能，這需要使用知道存在多少元素的數據結構。

來源

2014-07-05 09:48:32 amalloy

我不明白操作的漸近複雜性是如何實現的。當然''fromList'的*完全評估*花費O（n）時間，但對map'的完整評估也是如此，但花10 $ map f [1 ..]'不需要無限的時間，因爲評價是懶惰的。 – Bakuriu

在某些向量操作中不需要懶惰

回答

相關問題