haskell - Fingertree头复杂度

Question

我刚刚第二次阅读Apfelmus 对手指树的精彩介绍，并开始怀疑他对 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'我希望有一个小的常数因子差异有利于head（可能对此有 60% 的信心——列表融合优化的东西在工作时非常疯狂）。