sorts-and-trees.hs

import Data.List as List

data Tree a =
  Empty  |
  Leaf a |
  Branch (Tree a) a (Tree a) deriving Show

insertT :: Ord a => a -> Tree a -> Tree a

insertT n Empty = Leaf n

insertT n (Leaf m) =
  if n < m then
    Branch (Leaf n) m Empty
  else
    Branch Empty m (Leaf n)

insertT n (Branch left m right) =
  if n < m then
    Branch (insertT n left) m right
  else
    Branch left m (insertT n right)

buildTree :: Ord a => [a] -> Tree a
buildTree = foldr insertT Empty

sampList = [ 98, 21, 31, 74, 45, 24, 79, 11, 57, 18, 8, 65, 15, 9, 5, 7, 4, 80, 99, 49, 77, 40, 36, 16, 42, 61, 38, 32, 52, 39, 95, 72, 87, 53, 35, 22, 19, 48, 89, 69, 100, 50, 93, 86, 71, 27, 62, 2, 12, 63, 14, 29, 88, 3, 43, 75, 64, 68, 67, 30, 94, 59, 96, 20, 17, 23, 81, 46, 51, 47, 41, 28, 73, 66, 76, 78, 6, 70, 60, 26, 44, 58, 33, 55, 34, 54, 82, 84, 25, 83, 97, 90, 37, 56, 92, 13, 85, 1, 91, 10 ]

flatten' :: [a] -> Tree a -> [a]
flatten' accum (Branch left n right) = flatten' (n : (flatten' accum right)) left
flatten' accum (Leaf n) = n : accum
flatten' accum Empty = accum

flatten = flatten' []

quick :: Ord a => [a] -> [a]
quick [] = []
quick (x:xs) =
  let smaller = fst sorted
      bigger  = snd sorted
  in (quick smaller) ++ [x] ++ (quick bigger)
  where sorted = List.partition (< x) xs

quickTree :: Ord a => [a] -> Tree a
quickTree [] = Empty
quickTree (x:xs) =
  let smaller = fst sorted
      bigger = snd sorted
  in Branch (quickTree smaller) x (quickTree bigger)
  where sorted = List.partition (< x) xs

countTree :: Tree a -> Int
countTree (Branch left _ right) = 1 + (countTree left) + (countTree right)
countTree _ = 1

-- tree = buildTree sampList
-- tree' = quickTree sampList
-- countTree tree
-- countTree tree'

-- sorted = quick sampList
-- sorted' = flatten $ quickTree sampList