-- 2-3 trees. Notice how awkward the code is!
-- This is why we use AA trees instead.

data Tree a =
    Nil
  | Two (Tree a) a (Tree a)
  | Three (Tree a) a (Tree a) a (Tree a)
  deriving Show

member :: Ord a => a -> Tree a -> Bool
member _ Nil = False
member x (Two l y r)
  | x <  y = member x l
  | x == y = True
  | x >  y = member x r
member x (Three l y m z r)
  | x <  y = member x l
  | x == y = True
  | x <  z = member x m
  | x == z = True
  | x >  z = member x r

-- The insert function also must return whether the node was split or not.
data Insertion a = NoSplit (Tree a) | Split (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x t =
  case insert' x t of
    NoSplit t' -> t'
    Split l y r -> Two l y r

-- Lots of horrible case analysis, eurgh!
insert' :: Ord a => a -> Tree a -> Insertion a
insert' x Nil = Split Nil x Nil
insert' x (Two l y r)
  | x < y =
    case insert' x l of
      NoSplit l'   -> NoSplit (Two l' y r)
      Split l' z m -> NoSplit (Three l' z m y r)
  | x == y = NoSplit (Two l y r)
  | x > y =
    case insert' x r of
      NoSplit r' -> NoSplit (Two l y r')
      Split m z r' -> NoSplit (Three l y m z r')
insert' x (Three l y m z r)
  | x < y =
    case insert' x l of
      NoSplit l' -> NoSplit (Three l' y m z r)
      Split ll ly lr ->
        Split (Two ll ly lr) y (Two m z r)
  | x == y =
    NoSplit (Three l y m z r)
  | x > y && x < z =
    case insert' x m of
      NoSplit m' -> NoSplit (Three l y m' z r)
      Split ml my mr ->
        Split (Two l y ml) my (Two mr z r)
  | x == z = NoSplit (Three l y m z r)
  | x > z =
    case insert' x r of
      NoSplit r' -> NoSplit (Three l y m z r')
      Split rl rz rr ->
        Split (Two l y m) z (Two rl rz rr)