Advertisement
ttaaa

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.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement