Search code examples
haskelltime-complexityfinger-tree

Fingertree head complexity

I was just reading Apfelmus' excellent introduction to Finger Trees for the second time and started to wonder about his implementation of 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

As implementing functions in terms of one another is a quite nice way of reusing code, it got me thinking if the following implementation would be as efficient (complexity wise) as his original:

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

Is lazy evaluation as efficient as the original implementation?

Solution

  • Yes, head and head' should have the same time complexity if handed to GHC. I would expect a small constant-factor difference in favor of head (maybe 60% confident of this -- the list fusion optimization stuff is pretty wild when it works).