Splay tree in a pattern matching way
Hi, I checked the Hackage Splay Tree implementation from. http://hackage.haskell.org/packages/archive/TreeStructures/0.0.1/doc/html/sr... 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/algoxyhttp://sites.google.com/site/algoxy/home
Hi,
I just tried a smoke test case, seems the tree is balanced enough:
import System.Random
lookup :: (Ord a) => STree a -> a -> STree a
lookup E _ = E
lookup t@(Node l x r) y
| x == y = t
| x > y = splay (Node (lookup l y) x r) y
| otherwise = splay (Node l x (lookup r y)) y
testSplay = do
xs <- sequence (replicate 100 (randomRIO(1, 10)))
putStrLn $ show (foldl lookup t xs)
where
t = foldl insert (E::STree Int) [1..10]
Where STree a and insert are defined as in my previous email, except I
changed `x
Hi,
I checked the Hackage Splay Tree implementation from.http://hackage.haskell.org/packages/archive/TreeStructures/0.0.1/doc/...
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 tohttp://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 Xinyuhttp://sites.google.com/site/algoxyhttp://sites.google.com/site/algoxy/home
_______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
participants (2)
-
larry.liuxinyu -
Xinyu LIU