haskell - 指头复杂度

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

是的，head和 head'如果交给 GHC，应该具有相同的时间复杂度。我希望有一个小的常数因子差异有利于 head (也许有 60% 的信心 - 列表融合优化的东西在工作时非常疯狂)。