okasaki

commit 3f338e6e2a2589e14b345b74364c301dd0f4905c
parent 89bfceed8831e033f0b96a05a27705069182dccc
Author: Jared Tobin <jared@jtobin.ca>
Date:   Fri, 28 Nov 2014 19:15:19 +1300

Splay heap start.

Diffstat:
A
SplayHeap.hs
 | 
24
++++++++++++++++++++++++

1 file changed, 24 insertions(+), 0 deletions(-)
diff --git a/SplayHeap.hs b/SplayHeap.hs
@@ -0,0 +1,24 @@
+{-# OPTIONS_GHC -Wall #-}
+
+module SplayHeap where
+
+data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show
+
+insert :: Ord a => a -> Tree a -> Tree a
+insert x t = Node (smaller x t) x (bigger x t)
+
+bigger :: Ord a => a -> Tree a -> Tree a
+bigger _ Leaf = Leaf
+bigger pivot (Node a x b)
+  | x <= pivot = bigger pivot b
+  | otherwise  = case a of
+      Leaf       -> Node Leaf x b
+      Node l y r ->
+        if   y <= pivot
+        then Node (bigger pivot r) x b
+        else Node (bigger pivot l) y (Node r x b)
+
+-- FIXME
+smaller :: a
+smaller = undefined
+