treap.hs

data Vertice prior key = Vertice prior key deriving Show
data Treap p k = Nil | Branch (Treap p k) (Vertice p k) (Treap p k) deriving Show

-- simple in-order traversal
instance Foldable (Treap p) where
	foldr f acc Nil = acc
	foldr f acc (Branch left (Vertice p k) right) = 
		foldr f (f k $ foldr f acc right) left

insert :: (Ord k, Ord p) => Vertice p k -> Treap p k -> Treap p k
insert (Vertice key prior) Nil = Branch Nil (Vertice key prior) Nil
insert vertice@(Vertice prior key) treap@(Branch lt (Vertice prior' key') rt) = 
	case (compare key key', prior < prior') of
		(LT, True) -> Branch (insert vertice lt) (Vertice prior' key') rt
		(GT, True) -> Branch lt (Vertice prior' key') (insert vertice rt)
		otherwise -> treap

split :: (Ord k, Ord p) => Treap p k -> k -> (Treap p k, Treap p k) -> (Treap p k, Treap p k)
split Nil _ result = result
split treap@(Branch lt (Vertice prior' key') rt) key (left, right) = case compare key' key of
	LT -> (insert (Vertice prior' key') left, right)
	GT -> (left, insert (Vertice prior' key') right)
	otherwise -> (left, right)

-- left keys should be lesser than right keys
mergeable :: Ord a => [a] -> [a] -> Bool
mergeable lkeys rkeys = case (lkeys, rkeys) of
	(l:ls, r:rs) -> if (l < r) then mergeable ls rs else False
	otherwise -> True

example :: Treap Integer Integer
example = Branch Nil (Vertice 1 5) Nil

main = print $ mergeable 
	(foldr (:) [] $ insert (Vertice 0 4) example)
	(foldr (:) [] $ insert (Vertice 0 6) example)