[Haskell-cafe] Re: Splay tree in a pattern matching way

[larry.liuxinyu]

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<y' to `x>y' (sorry for the mistake).
By running the testSplay I got a BST like this:

*SplayHeap> testSplay
Node (Node E 1 (Node (Node E 2 E) 3 (Node (Node E 4 (Node E 5 E)) 6
(Node E 7 E)))) 8 (Node (Node E 9 E) 10 E)

So I got a bit more confident about the correctness of my code.

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

On Oct 24, 11:06 am, Xinyu LIU <liuxiny... at gmail.com> wrote:
> 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/algoxy<http://sites.google.com/site/algoxy/home>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-C... at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe