手指树头复杂度

Question

刚读完Apfelmus' excellent introduction to Finger Trees第二遍，开始好奇他的head实现：

import Prelude hiding (head)

data Tree v a = Leaf   v a
              | Branch v (Tree v a) (Tree v a)

toList :: Tree v a -> [a]
toList (Leaf _ a)     = [a]
toList (Branch _ x y) = toList x ++ toList y

head :: Tree v a -> a
head (Leaf _ a)     = a
head (Branch _ x _) = head x

由于相互实现功能是重用代码的一种很好的方式，这让我开始思考以下实现是否与他的原始实现一样高效（复杂性方面）：

import Prelude -- not needed, just for making it obvious
data Tree v a = Leaf   v a
              | Branch v (Tree v a) (Tree v a) deriving Show

toList :: Tree v a -> [a]
toList (Leaf _ a)     = [a]
toList (Branch _ x y) = toList x ++ toList y

head' :: Tree v a -> a
head' = head . toList

惰性评估是否与原始实施一样高效？

Answer 1

是的，如果交给 GHC，head 和 head' 应该具有相同的时间复杂度。我希望 constant-factor 有利于 head 的小差异（可能对此有 60% 的信心——列表融合优化的东西在工作时非常疯狂）。

手指树头复杂度

Fingertree head complexity

haskell

time-complexity

finger-tree