Can this implementation of in-order traversal of a

Question

I wrote a straightforward in-order-traversal function (toList1) for a binary tree. However, I worry about its complexity (memory / time). Is there a better way to implement it?

data Tree a = Empty | Node a (Tree a) (Tree a) 
toList1 :: (Tree a) -> [a]
toList1 Empty = []
toList1 (Node x lx rx) = (toList lx) ++ [x] ++ (toList rx)

Answer 1

Haskell's append ++ performs linearly in the length of its left argument, which means that you may get quadratic performance if the tree leans left. One possibility would be to use difference list.

Another one would be to define a Foldable instance:

data Tree a = Empty | Node a (Tree a) (Tree a)

instance Foldable Tree where
    foldr f z Empty = z
    foldr f z (Node a l r) = foldr f (f a (foldr f z r)) l

then, in-order-traversal comes out naturally:

toList :: Tree a -> [a]
toList = foldr (:) []

and

\> let tr = Node "root" (Node "left" Empty Empty) (Node "right" Empty Empty)
\> toList tr
["left","root","right"]