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

From HaskellWiki
Jump to: navigation, search
(categorize)
m (Minor formatting changes)
 
Line 14: Line 14:
 
</haskell>
 
</haskell>
  
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 <code>construct</code> is trivial, because the pattern of accumulating from the left is captured by the standard function <code>foldl</code>.
  
  
 
[[Category:Programming exercise spoilers]]
 
[[Category:Programming exercise spoilers]]

Latest revision as of 22:03, 23 April 2021

(**) 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.