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

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