Guest User

Untitled

a guest
Oct 15th, 2021
194
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- BINARY SEARCH TREE (BinaryTree)
  2. -- LEFT FROM = -> type constructor -> cant be created as value
  3. -- RIGHT FROM = -> value constructor -> can be created as value
  4. -- -> There will never be BinaryTree 1 as value. Since BinaryTree 1 is either EmptyTree or
  5. -- Node 1 (EmptyTree | Node val (EmptyTree | Node val ....))
  6. data BinaryTree a
  7.   = EmptyTree
  8.   | Node a (BinaryTree a) (BinaryTree a)
  9.   deriving (Show, Read, Eq)
  10.  
  11. -- helper function that determines whether the tree is empty.
  12. isEmptyTree :: BinaryTree a -> Bool
  13. isEmptyTree EmptyTree = True
  14. isEmptyTree _ = False
  15.  
  16. -- helper function that creates a base tree(node empty empty) for given number.
  17. createBaseTree :: a -> BinaryTree a
  18. createBaseTree x = Node x EmptyTree EmptyTree
  19.  
  20. -- three cases: eq -> drop, bigger -> right, smaller -> left
  21. -- Notation: first BinaryTree(a) is the left leaf and second BinaryTree(a) is the right leaf.
  22. insertInBinaryTree :: (Ord a) => BinaryTree a -> a -> BinaryTree a
  23. insertInBinaryTree EmptyTree input = Node input EmptyTree EmptyTree
  24. insertInBinaryTree (Node x leftTree rightTree) input
  25.   | input == x = Node x leftTree rightTree
  26.   | input < x =
  27.     if isEmptyTree leftTree
  28.       then Node x (createBaseTree input) rightTree
  29.       else Node x (insertInBinaryTree leftTree input) rightTree
  30.   | input > x =
  31.     if isEmptyTree rightTree
  32.       then Node x leftTree (createBaseTree input)
  33.       else Node x leftTree (insertInBinaryTree rightTree input)
  34.  
  35. -- generate some numbers to insert into tree
  36. genNumbers = map (\x -> if even x then x + 10 else x) [1 .. 5]
  37.  
  38. -- test implementation by inserting numbers into BinaryTree with base 10
  39. insertNumbersIntoTree =
  40.   foldl (\acc x -> insertInBinaryTree acc x) (createBaseTree 10) genNumbers
  41.  
RAW Paste Data