Сложность головы пальцем

Question

Я только что прочитал Отличное введение Апфельма в Finger Trees во второй раз и начал задумываться о его реализации головы:

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% уверены в этом - оптимизация слияния списков довольно дикая, когда она работает).