Monitor puzzle

README.md

It's 8AM on a Monday and Joel is trying to get in to the Nitor Office.

Joel has lots of keys in a keychain in his pocket. Each key can have a parent key that it hangs on, and possibly a left or a right child key that hang on it.

Joel gropes around in his pocket for the leftmost key. This can be reached by starting at the top key, and moving to the lefth child key as long as possible. After this Joel pulls the keychain out of his pocket using this key. The rest of the keys dangle under this new top key.

Examples:

     a                b
   /   \             / \
 b      d     ==>   c   a
  \    / \               \
   c  e   f               d
                         / \
                        e   f

     a               d
    / \               \
   b   c               b
  / \        ==>      / \
 d   e               e   a
    / \             / \   \
   f   g           f   g   c

What happens in the following situation?

[hide answer]
       a            g
     /   \           \
   b      c           d
  / \    /   ==>     / \
 d   e  f           h   b
/ \                    / \
g  h                  e   a
                           \
                           c
                          /
                         f

Can you write a program that does this?

solution.hs

data Tree = Empty | Node Char Tree Tree
  deriving (Show, Eq)

pivot Empty = Empty
pivot (Node c l r) = go l (Node c Empty r)
  where go Empty rest = rest
        go (Node c l r) rest = go l (Node c r rest)

input = Node 'a' (Node 'b' (Node 'd' (Node 'g' Empty Empty) (Node 'h' Empty Empty))
                           (Node 'e' Empty Empty))
                 (Node 'c' (Node 'f' Empty Empty) Empty)

-- > pivot input
-- Node 'g' Empty (Node 'd' (Node 'h' Empty Empty) (Node 'b' (Node 'e' Empty Empty) (Node 'a' Empty (Node 'c' (Node 'f' Empty Empty) Empty))))