2

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?

Fabian Schneider
  • 799
  • 1
  • 13
  • 40
  • related: [Haskell foldl' poor performance with (++)](https://stackoverflow.com/a/14942678/849891), [Why are difference lists more efficient than regular concatenation in Haskell?](https://stackoverflow.com/q/13879260/849891), [Explicit Purely-Functional Data-Structure For Difference Lists](https://stackoverflow.com/q/43941551/849891). – Will Ness Jul 31 '21 at 10:34

1 Answers1

2

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).

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • 1
    @FabianSchneider I have deleted that comment. It was due to sloppy thinking on my part. But to answer your question anyway: "space leak" means keeping something in memory even though it will demonstrably not be needed later. – Daniel Wagner May 09 '19 at 14:31