Elm example: http://elm-lang.org/examples/binary-tree

BinaryTree.elm

{- OVERVIEW ------------------------------------------------------

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 Html exposing (Html, div, span, text, node)
import Html.Attributes exposing (type_, style, class)



-- TREES


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 then
              Node y left (insert x right)

          else if x < y then
              Node y (insert x left) right

          else
              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)


map2 : (comparable -> comparable) -> Tree comparable -> Tree comparable
map2 f =
  fold (\a -> insert (f a)) Empty


sum : Tree number -> number
sum tree =
  case tree of
    Empty -> 0
    Node v left right ->
      v + (sum left) + (sum right)


sum2 : Tree number -> number
sum2 = fold (+) 0


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


flatten2 : Tree a -> List a
flatten2 = fold (::) []


isElement : comparable -> Tree comparable -> Bool
isElement x tree =
  case tree of
    Empty -> False
    Node y left right ->
      if y == x then
        True
      else if x < y then
        isElement x left
      else
        isElement x right


isElement2: a -> Tree a -> Bool
isElement2 x =
  fold (\v ok -> ok || v == x) False


fold : (a -> b -> b) -> b -> Tree a -> b
fold f init tree =
  case tree of
    Empty ->
      init
      
    Node v left right ->
      fold f init left
        |> f v
        |> (\b -> fold f b right)


reduce : (a -> b -> b -> b) -> b -> Tree a -> b
reduce f init tree =
  case tree of
    Empty ->
      init
    
    Node v left right ->
      let
        bl = reduce f init left
        br = reduce f init right
      in
        f v bl br


-- PLAYGROUND


deepTree =
  fromList [5,1,9,3,8,2,7]


niceTree =
  fromList [2,1,3]


main : Html msg
main =
  div [ style [ ("font-family", "monospace") ] ]
    [ display "deepTree" deepTree
    , display "niceTree" niceTree
    , display "depth niceTree" (depth niceTree)
    , display "incremented niceTree" (map (\n -> n + 1) niceTree)
    , display "incremented2 niceTree" (map2 (\n -> n + 1) niceTree)
    , display "sum niceTree" (sum niceTree)
    , display "sum2 niceTree" (sum2 niceTree)
    , display "flatten deepTree" (flatten deepTree)
    , display "flatten niceTree" (flatten niceTree)
    , display "flatten2 deepTree" (flatten2 deepTree)
    , display "flatten2 niceTree" (flatten2 niceTree)
    , display "isElement 1 niceTree" (isElement 1 niceTree)
    , display "isElement 2 niceTree" (isElement 2 niceTree)
    , display "isElement 4 niceTree" (isElement 4 niceTree)
    , display "isElement2 1 niceTree" (isElement2 1 niceTree)
    , display "isElement2 2 niceTree" (isElement2 2 niceTree)
    , display "isElement2 4 niceTree" (isElement2 4 niceTree)
    , display "fold 0 niceTree" (fold (\a b -> a + b) 0 niceTree)
    , viewTree deepTree
    ]


display : String -> a -> Html msg
display name value =
  div [] [ text (name ++ " ==> " ++ toString value) ]


viewTree : Tree a -> Html msg
viewTree =
  reduce
    (\v left right ->
      div
        [ style
            [ ("border", "1px solid black")
            , ("padding", "3px")
            , ("display", "inline-block")
            , ("margin", "1px")
            ]
        ]
        [ div [] [text (toString v)]
        , left
        , right
        ])
    (text "")


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

Exercises:

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

       sum : Tree number -> number

(2) Flatten a tree into a list.

       flatten : Tree a -> List a

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

       isElement : a -> Tree a -> Bool

(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

(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!

(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

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