Hi,

I checked the Hackage Splay Tree implementation from.
http://hackage.haskell.org/packages/archive/TreeStructures/0.0.1/doc/html/src/Data-Tree-Splay.html#SplayTree

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 according to
http://en.wikipedia.org/wiki/Splay_tree

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
-- zig-zig
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
-- zig-zag
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
-- zig
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
-- otherwise
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.

Regards.

--
Larry. LIU Xinyu
http://sites.google.com/site/algoxy