Finger Tree的head实现复杂度对比：惰性求值是否等价原实现？

Great question! Let’s dig into how Haskell’s lazy evaluation affects these two implementations, and whether their time complexities are equivalent.

First, let’s recap the two approaches:

Original Recursive head Implementation #

import Prelude hiding (head)
data Tree v a = Leaf v a | Branch v (Tree v a) (Tree v a)
head :: Tree v a -> a
head (Leaf _ a) = a
head (Branch _ x _) = head x

This implementation directly traverses the leftmost path of the tree, recursively diving into the left child of each Branch until it hits a Leaf. The time complexity here is O(d), where d is the depth of the leftmost leaf (for a balanced tree like a finger tree, this is O(log n)).

Reusable head' = head . toList Implementation #

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

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

At first glance, you might worry that toList would generate the entire list before head can grab the first element—but Haskell’s lazy evaluation prevents that entirely.

Here’s what actually happens when you call head' on a tree:

• head demands the first element of the list returned by toList.
• For a Branch, toList evaluates to toList x ++ toList y. In Haskell, the (++) operator is lazy: it doesn’t evaluate the entire left list or touch the right list until needed. To get the first element of toList x ++ toList y, it only needs the first element of toList x.
• This triggers the same recursive traversal as the original head function: toList x will recursively dive into the leftmost Branch until it hits a Leaf, then return [a]. The first (and only) element of this list is immediately passed to head.
• None of the rest of toList x or any of toList y is ever evaluated—lazy evaluation stops as soon as the required value is available.

Conclusion #

In short: yes, the time complexity of both implementations is exactly equivalent under Haskell’s lazy evaluation. Both will only traverse the leftmost path of the tree to the first Leaf, with no extra work done on the rest of the tree.

The tradeoff here is readability and code reuse vs. minimal overhead:

• The head . toList version is more concise and reuses existing code (following the DRY principle), which is great for maintainability.
• The recursive version avoids the tiny overhead of constructing a single cons cell (:) for the list element, but this is negligible in almost all cases.

内容的提问来源于stack exchange，提问作者Fabian Schneider