[Haskell-cafe] Splay tree in a pattern matching way
liuxinyu95 at gmail.com
Sat Oct 23 23:06:07 EDT 2010
I checked the Hackage Splay Tree implementation from.
Basically it's based on the strategy mentioned in Okasaki's ``Purely
Functional Programming'', Chapter 5.4.
That in case we traverse twice in left (or right), we rotate the tree, so in
long term of view, the tree turns more and more balanced.
There are 3 cases for splay: zig-zig case, zig-zag case and zig case
So I wonder if Splay tree can also be implemented by using pattern matching
in a similar way as red black tree.
Here is a draft source code:
data STree a = E -- Empty
| Node (STree a) a (STree a) -- left, element, right
deriving (Eq, Show)
-- splay by pattern matching
splay :: (Eq a) => STree a -> a ->STree a
splay t@(Node (Node (Node a x b) p c) g d) y =
if x == y then Node a x (Node b p (Node c g d)) else t
splay t@(Node a g (Node b p (Node c x d))) y =
if x == y then Node (Node (Node a g b) p c) x d else t
splay t@(Node (Node a p (Node b x c)) g d) y =
if x == y then Node (Node a p b) x (Node c g d) else t
splay t@(Node a g (Node (Node b x c) p d)) y =
if x == y then Node (Node a g b) x (Node c p d) else t
splay t@(Node (Node a x b) p c) y = if x == y then Node a x (Node b p
c) else t
splay t@(Node a p (Node b x c)) y = if x == y then Node (Node a p b) x
c else t
splay t _ = t
-- insert by using pattern matching
insert :: (Ord a) => STree a -> a -> STree a
insert E y = Node E y E
insert (Node l x r) y
| x < y = splay (Node (insert l y) x r) y
| otherwise = splay (Node l x (insert r y)) y
I am not quite sure if the solution is correct and what about the
efficiency of this code.
Larry. LIU Xinyu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe