Some stuff related to http://deni-ok.livejournal.com/38228.html

TestTree.hs

import Test.QuickCheck
import Tree

prop_id [] = True
prop_id xs = xs == (toList . fromList) xs

prop_elem x xs = (x `elem` xs) == (x `elemTree` fromList xs)

Tree.hs

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

instance Show a => Show (Tree a) where
  show = show . toList

toList :: Tree a -> [a]
toList = go . return
  where go :: [Tree a] -> [a]
        go ((Branch a l r):xs) = a : go (xs ++ [l,r]) -- Here we go massive BFSing.
        go _ = []

fromList :: [a] -> Tree a
fromList (x:xs) = Branch x (fromList l) (fromList r)
  where (l, r) = go xs [] [] 1
        go [] al ar _ = (al, ar)
        go ys al ar k = go (drop (2*k) ys) (al ++ take k ys) (ar ++ take k (drop k ys)) (2*k)
fromList [] = Empty

elemTree :: Eq a => a -> Tree a -> Bool
elemTree x t = x `elem` toList t