Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Aug 1st, 2012  |  syntax: None  |  size: 1.67 KB  |  hits: 7  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. Monad BinTree
  2.  
  3. > import Data.Maybe
  4. > import Control.Monad
  5. > data BinTree a = Empty | Branch {left :: BinTree a ,  val :: a, right:: BinTree a} deriving Show
  6.  
  7. > isBST :: BinTree a -> Bool
  8. > isBST Empty = True
  9. > isBST (Branch Empty b Empty) = True
  10. > isBST (Branch a b Empty) = if (fromJust (largest a) > b) then False else isBST a
  11. > isBST (Branch Empty b c) = if (b > fromJust (smallest c)) then False else isBST c
  12. > isBST (Branch a b c) = if isBST (Branch a b Empty) && isBST (Branch Empty b c) then True else False
  13.  
  14. > largest :: Ord a => BinTree a -> Maybe a
  15. > largest Empty = Nothing
  16. > largest (Branch Empty b Empty) = Just b
  17. > largest (Branch a b Empty) = if largest a < b then Just b else Just (largest a)
  18. > largest (Branch Empty b c) = if largest c < b then Just b else Just (largest c)
  19. > largest (Branch a b c) = if largest c > largest a then Just largest (Branch Empty b (Branch Empty (largest c) Empty)) else Just largest (Branch (Branch Empty (largest a) Empty) b Empty)
  20.  
  21. > smallest :: Ord a => BinTree a -> Maybe a
  22. > smallest Empty = Nothing
  23. > smallest (Branch Empty b Empty) = Just b
  24. > smallest (Branch a b Empty) = if smallest a > b then Just b else Just (smallest a)
  25. > smallest (Branch Empty b c) = if smallest c > b then Just b else Just (smallest c)
  26. > smallest (Branch a b c) = if smallest c < smallest a then Just smallest (Branch Empty b (Branch Empty (smallest c) Empty)) else Just smallest (Branch (Branch Empty (smallest a) Empty) b Empty)
  27.  
  28.  addBST :: BinTree a -> BinTree a -> a -> BinTree a
  29.  
  30.  removeLargestBST :: BinTree a -> (a, BinTree a)
  31.  removeLargestBST Empty = ((), Empty)
  32.  
  33.  removeLargestBST
  34.  
  35.  
  36.  removeSmallestBST :: BinTree a -> (a, BinTree a)
create a new version of this paste RAW Paste Data