Nik*_* B. 3 haskell sequence lazy-evaluation data-structures
以下示例显示了我们遇到的问题Data.Sequence:
{-# LANGUAGE BangPatterns #-}
module Main where
import qualified Data.Sequence as S
import Data.Sequence ((|>), ViewL(..))
import Data.List (foldl')
import GHC.AssertNF
update !init !x = init |> x
main =
do let !seq = foldl' update S.empty [1..10]
assertNF seq
它打印
Parameter not in normal form: 1 thunks found:
Deep (One (S# 1)) (_thunk (Deep (One ...) (_thunk ... ... ... ...) (Three ... ... ...) 93) (S# 95) (S# 96) (S# 97)) (Three (S# 98) (S# 99) (S# 100)) 100
但是,Data.Sequence所有操作都严格的声明文档,为什么插入后树没有完全评估？是否需要保证一些非常复杂的界限？
我们在这里不太喜欢懒惰,所以我想知道是否有一个更严格|>或类似的数据结构支持从后面追加到后面和枚举,可能是一个更有效的？
Don*_*art 13
Data.Sequence是一个元素严格,数字严格的数据结构,具有惰性脊柱.
data FingerTree a
= Empty
| Single a
| Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
这意味着将对已插入的值进行评估存储,但仅在查询时评估结构的主干.这通常是你想要的 - 较小的数据结构.
如果你想对它施加一个严格的脊椎,你将会产生更大的插入成本,但你可能会获得其他地方.
尝试将fingertrees包修改为spine严格并查看它是否实际更快 - 我将有兴趣知道结果.
顺便说一句:"我们不喜欢这里的懒惰",这不是避免脊柱懒惰数据结构的好理由.如果[a]是严格的脊椎,那将是一种可怕的数据类型.Data.Sequence也是如此.您应该量化为什么spine-strictness是您的用例的错误语义.
Pet*_*lák 11
手指树的良好表现取决于懒惰.引用Hinze,Ralf; Paterson,Ross(2006),"手指树:简单的通用数据结构":
...虽然结构基本上使用了懒惰,但它也适用于提供惰性评估原语的严格语言.
并在分析其属性时:
......因此,在一系列操作中,平均成本是不变的.
如果使用延迟评估暂停子树,则相同的边界在持久设置中保持.这确保了在后续操作需要向下移动那么之前不会发生脊柱深处的变换.由于上述安全和危险数字的特性,到那个时候,已经进行了足够便宜的浅层操作来支付这种昂贵的评估费用.
因此,如果将实现从惰性更改为严格,则可能会失去良好的时间复杂性界限(取决于您使用的操作和顺序).