Seeing and Doing :
From doing to seeing
The structure that emerges is a binary search tree. This reveals the
following alternative formulation of quicksort:
treesort xs = flatten (foldr insert Empty xs)
data Tree a = Empty | Node a (Tree a) (Tree a)
insert a Empty = Node a Empty Empty
insert a (Node b l r) = if a<=b
then Node b (insert a l) r
else Node b l (insert a r)
flatten t = flatten' t []
where
flatten' Empty = id
flatten' (Node a l r) = flatten' l . (a:) . flatten' r