Difference between revisions of "99 questions/Solutions/57"

From HaskellWiki
Jump to: navigation, search
 
(categorize)
 
Line 15: Line 15:
   
 
Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl.
 
Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl.
  +
  +
  +
[[Category:Programming exercise spoilers]]

Latest revision as of 13:37, 25 December 2016

(**) Binary search trees (dictionaries)

Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers.

add :: Ord a => a -> Tree a -> Tree a
add x Empty            = Branch x Empty Empty
add x t@(Branch y l r) = case compare x y of
                            LT -> Branch y (add x l) r
                            GT -> Branch y l (add x r)
                            EQ -> t

construct xs = foldl (flip add) Empty xs

Here, the definition of construct is trivial, because the pattern of accumulating from the left is captured by the standard function foldl.