3

以下示例显示了我们遇到的问题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声称所有操作都是严格的文档，那么为什么在插入后没有对树进行完全评估？是否需要保证一些摊销的复杂性界限？

我们这里不是很喜欢懒惰，所以不知道有没有更严格|>或者类似的数据结构，支持后面追加和前面枚举，可能更高效？

4

2 回答 2

13

Data.Sequence 是一个元素严格、数字严格的数据结构，具有惰性脊椎。

data FingerTree a
    = Empty
    | Single a
    | Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)

这意味着插入的值将被存储评估，但结构的脊椎将仅在查询时评估。这通常是您想要的——更小的数据结构。

如果您想对其施加严格的脊椎，您将承担更大的插入成本，但您可能会在其他地方获得收益。

尝试将fingertrees 包修改为spine strict，看看它是否真的更快——我很想知道结果。

顺便说一句：“我们在这里不太喜欢懒惰”，这不是避免脊椎懒惰数据结构的好理由。如果 [a] 是严格的，那将是一个糟糕的数据类型。Data.Sequence 可能也是如此。您应该量化为什么脊椎严格性对于您的用例来说是错误的语义。

于 2013-02-08T11:04:43.187 回答
11

手指树的良好性能取决于惰性。引用拉尔夫 Hinze 的话；Paterson, Ross (2006)，“手指树：一种简单的通用数据结构”：

...虽然该结构本质上使用了惰性，但它也适用于提供惰性求值原语的严格语言。

并在分析其属性时：

...因此，在一系列操作中，平均成本是恒定的。

如果子树使用惰性评估挂起，则相同的界限在持久设置中成立。这确保了在后续手术需要深入到那么远之前，不会发生脊柱深处的转变。由于安全和危险数字的上述特性，到那时将执行足够便宜的浅层操作来支付这种昂贵的评估费用。

因此，如果您将实现从惰性更改为严格，您可能会失去良好的时间复杂度界限（取决于您使用的操作和顺序）。

于 2013-02-08T12:54:38.007 回答