Elm BST challenges

BST.elm

{-----------------------------------------------------------------

A "Tree" represents a binary tree. A "Node" in a binary tree
always has two children. A tree can also be "Empty". Below I have
defined "Tree" and a number of useful functions.

This example also includes some challenge problems :)

-----------------------------------------------------------------}

import Graphics.Element exposing (..)
import Text


type Tree a
    = Empty
    | Node a (Tree a) (Tree a)


empty : Tree a
empty =
    Empty


singleton : a -> Tree a
singleton v =
    Node v Empty Empty


insert : comparable -> Tree comparable -> Tree comparable
insert x tree =
    case tree of
      Empty ->
          singleton x

      Node y left right ->
          if  | x > y -> Node y left (insert x right)
              | x < y -> Node y (insert x left) right
              | otherwise -> tree


fromList : List comparable -> Tree comparable
fromList xs =
    List.foldl insert empty xs


depth : Tree a -> Int
depth tree =
    case tree of
      Empty -> 0
      Node v left right ->
          1 + max (depth left) (depth right)


map : (a -> b) -> Tree a -> Tree b
map f tree =
    case tree of
      Empty -> Empty
      Node v left right ->
          Node (f v) (map f left) (map f right)


t1 = fromList [1,2,3]
t2 = fromList [2,1,3,4]


main : Element
main =
    flow down
        [ display "depth" depth t1
        , display "depth" depth t2
        , display "map ((+)1)" (map ((+)1)) t2
        , display "sum" sum t2
        , display "flatten" flatten t2
        , display "isElement" (isElement 5) t2
        , display "isElement" (isElement 4) t2
        ]


display : String -> (Tree a -> b) -> Tree a -> Element
display name f value =
    name ++ " (" ++ toString value ++ ") &rArr;\n    " ++ toString (f value) ++ "\n "
        |> Text.fromString
        |> Text.monospace
        |> leftAligned


{-----------------------------------------------------------------

Exercises:

(1) Sum all of the elements of a tree.

       sum : Tree Number -> Number
--}
sum : Tree Int -> Int
sum tree =
    case tree of
      Empty -> 0

      Node v left right ->
        v + sum left + sum right

{--
(2) Flatten a tree into a list.

       flatten : Tree a -> List a
--}
flatten : Tree a -> List a
flatten tree =
    case tree of
      Empty -> []
      Node v left right ->
        List.concat [[v], (flatten left), (flatten right)]

{--


(3) Check to see if an element is in a given tree.

       isElement : a -> Tree a -> Bool
--}
isElement : a -> Tree a -> Bool
isElement x tree =
    case tree of
      Empty -> False
      Node y left right -> y == x
                        || isElement x left
                        || isElement x right

{--
(4) Write a general fold function that acts on trees. The fold
    function does not need to guarantee a particular order of
    traversal.

       fold : (a -> b -> b) -> b -> Tree a -> b
--}
fold : (a -> b -> b) -> b -> Tree a -> b
fold f init tree =
    case tree of
      Empty -> init
      Node z left right ->
        (fold f (f z (fold f init right)) left)

{--
(5) Use "fold" to do exercises 1-3 in one line each. The best
    readable versions I have come up have the following length
    in characters including spaces and function name:
      sum: 16
      flatten: 21
      isElement: 46
    See if you can match or beat me! Don't forget about currying
    and partial application!
--}
summary1 : List Element
summary1 =
  let sum = fold (+) 0
      flatten = fold (::) []
      isElement e = fold ((==) e >> (||)) False
  in  [ display "fold: sum t1"         sum t1
      , display "fold: flatten t1"     flatten t1
      , display "fold: isElement 1 t1" (isElement 1) t1
      , display "fold: isElement 2 t1" (isElement 2) t1
      , display "fold: isElement 3 t1" (isElement 3) t1
      , display "fold: isElement 4 t1" (isElement 4) t1
      ]


{--
(6) Can "fold" be used to implement "map" or "depth"?

--}
{--
(7) Try experimenting with different ways to traverse a
    tree: pre-order, in-order, post-order, depth-first, etc.
    More info at: http://en.wikipedia.org/wiki/Tree_traversal
--}