# BTree

Jan 16th, 2022
768
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. module BinomialTree
2.    (
3.       BinTree,
4.       key,
5.       rank,
6.       children,
7.       createTree,
8.       mergeTrees,
9.       treeFoldr,
10.       treeFoldl
11.    ) where
12.
13. data (Eq a, Ord a) => BinTree a = BTree a Int [BinTree a] deriving (Eq, Show)
14.
15. key :: Ord a => BinTree a -> a
16. key (BTree a _ _) = a
17.
18. rank :: Ord a => BinTree a -> Int
19. rank (BTree _ r _) = r
20.
21. children :: Ord a => BinTree a -> [BinTree a]
22. children (BTree _ _ c) = c
23.
24. createTree :: Ord a => a -> Int -> [BinTree a] -> BinTree a
25. createTree k r c = BTree k r c
26.
27. mergeTrees :: Ord a => BinTree a -> BinTree a -> BinTree a
28. mergeTrees t1 t2 =
29.    if key t1 <= key t2 then
30.       BTree (key t1) (rank t1 + 1) ((children t1) ++ [t2])
31.    else
32.       mergeTrees t2 t1
33.
34. treeFoldr :: Ord a => (a -> b -> b) -> b -> BinTree a -> b
35. treeFoldr f z (BTree k _ []) = f k z
36. treeFoldr f z (BTree k _ (hd:tl)) = treeFoldr f (treeFoldr f z hd) (BTree k 0 tl)
37.
38. treeFoldl :: Ord a => (b -> a -> b) -> b -> BinTree a -> b
39. treeFoldl f z (BTree k _ []) = f z k
40. treeFoldl f z (BTree k _ (hd:tl)) = treeFoldl f (treeFoldl f z (BTree k 0 tl)) hd
41.