Documented time bounds are incorrect for persistent use

[treeowl]

The usual assumption for pure data structures in Haskell is that the documented time bounds may be amortized, but that amortization must hold up under persistent use. That is not true for dlist. snoc and head are both documented as being O(1), and yet the following program runs far longer than I would ever want to wait. Swapping in Data.Sequence for DList lets this run quickly.

import qualified Data.DList as D
import Data.DList (DList)
import Data.Foldable

blob :: DList Int
blob = foldl' D.snoc mempty [1..10^7]

main :: IO ()
main = print $ sum [ D.head (blob `D.snoc` a) | a <- [1..10^6 :: Int]]

I think the best approach is likely to document that DLists are intended to be used in an affine/linear fashion, and that the bounds are only valid in that context.

[treeowl]

There's a lot of relevant discussion in Reflection Without Remorse: Revealing a hidden sequence to speed up monadic reflection, though the paper goes in a different direction.

[treeowl]

Hrm... affine use is putting too strong a point on it. It's perfectly fine to concat . replicate n a DList. But they should generally only be "inspected" once.

[Anton-Latukha]

Yep.

To unwrap example:

(also decreased magnitude one time, so it is faster/easier to play & get code responses)

import qualified Data.DList as D
import Data.DList (DList)
import qualified Data.Sequence as S
import Data.Sequence (Seq)
import Data.Foldable

-- DList
blobD :: DList Int
blobD = foldl1 (D.snoc) mempty [1..10^6]

mainD :: IO ()
mainD = print $ sum [ D.head (D.snoc blobD a) | a <- [1..10^5 :: Int]]

-- Seq
blobS :: Seq Int
blobS = foldl1 (S.|>) mempty [1..10^6]

mainS :: IO ()
mainS = print $ fmap sum [ S.take 1 (blobS S.|> a) | a <- [1..10^5 :: Int]]

The First would do not terminate in meaningful time, but the second terminates fast.

foldr would be the same.

[tom93]

The mistake in the docs is that the worst-case time complexity of head is not O(1). The examples in this issue demonstrate that in order to get the head of a DList, the program may need to traverse O(n) snoc nodes.

The actual worst-case time complexity of head is hard to specify. It is tempting to say "O(n) where n is the length of the DList", but it can actually be worse than that depending on the way the DList was constructed. The following variation of the original example constructs a DList of length 1 that is very slow to traverse:

import Data.DList as D
main = do
  -- Repeatedly prepend empty DLists to a singleton DList
  let xs = iterate (D.append mempty) (D.singleton 42) !! (10^6)
  print $ D.toList xs -- Output: [42] (so the length of `xs` is 1)
  print $ sum [D.head (xs `D.snoc` x) | x <- [1..10^6]] -- Total time complexity: 10^6 * 10^6