An Introduction to Elm Series: Solution to ‘Binary Tree’ example


In http://elm-lang.org/examples/binary-tree, we are given a basic implementation of a binary tree and we are asked to extend it in various ways.

To implement the Breadth First Traversal, we had to use another module that acts like a Queue. The code of that Queue is available at this post http://bytefreaks.net/programming-2/elm/an-introduction-to-elm-series-solution-to-binary-tree-example-supplementary-module-queue and it is also included in the zip file with the code of this solution ( binary-tree.elm (compressed) (115 downloads) ).

Below you will find our solutions to these challenges.

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

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


module Main exposing (..)

import Queue exposing (Queue)
import Html exposing (Html, div, text, br)
import Html.Attributes exposing (style)


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



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


sum : Tree number -> number
sum tree =
    case tree of
        Empty ->
            0

        Node value left right ->
            value + sum left + sum right



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


flatten : Tree a -> List a
flatten tree =
    case tree of
        Empty ->
            []

        Node value left right ->
            flatten left ++ [ value ] ++ flatten right



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


isElement : a -> Tree a -> Bool
isElement element tree =
    case tree of
        Empty ->
            False

        Node value left right ->
            -- We short circuit the evaluation, if we find early that the element is in the tree we stop the recursion down this path.
            if value == element then
                True
            else
                isElement element left || isElement element 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 function element tree =
    case tree of
        Node value left right ->
            function value (fold function (fold function element right) left)

        Empty ->
            element



{--(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!--}
-- The following functions are called as parameters for the fold function
-- Sum the values of all nodes in the tree


sumByFold : number -> number -> number
sumByFold elementA elementB =
    elementA + elementB



-- Flatten the tree in a pre-order fashion


flattenByFold : a -> List a -> List a
flattenByFold element list =
    [ element ] ++ list



-- Count the total number of nodes in the tree


countByFold : number -> number -> number
countByFold element count' =
    1 + count'



-- The following functions are using fold internally
-- Sum the values of all nodes in the tree


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



-- Flatten the tree in an in-order fashion


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



-- Checks if a certain element is in the tree


isElementUsingFold : a -> Tree a -> Bool
isElementUsingFold element =
    fold ((==) element >> (||)) False



-- (6) Can "fold" be used to implement "map" or "depth"?
-- TODO
{--(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--}
-- Depth-first


preOrder : Tree a -> List a
preOrder tree =
    case tree of
        Empty ->
            []

        Node value left right ->
            [ value ] ++ preOrder left ++ preOrder right


inOrder : Tree a -> List a
inOrder tree =
    case tree of
        Empty ->
            []

        Node value left right ->
            inOrder left ++ [ value ] ++ inOrder right


postOrder : Tree a -> List a
postOrder tree =
    case tree of
        Empty ->
            []

        Node value left right ->
            postOrder left ++ postOrder right ++ [ value ]



-- Breadth-first


go : Queue (Tree a) -> List a
go queue =
    let
        ( maybe', queue' ) =
            Queue.dequeue queue
    in
        case maybe' of
            Just node ->
                case node of
                    Empty ->
                        go queue'

                    Node value left right ->
                        [ value ] ++ go (Queue.enqueue right (Queue.enqueue left queue'))

            Nothing ->
                []


levelOrder : Tree a -> List a
levelOrder tree =
    case tree of
        Empty ->
            []

        Node value left right ->
            go (Queue.enqueue tree (Queue.init))



-- PLAYGROUND


deepTree =
    fromList [ 1, 2, 3 ]


niceTree =
    fromList [ 2, 1, 3 ]


deepTree' =
    fromList [ 1, 2, 3, 4, 5, 6, 7 ]


niceTree' =
    fromList [ 4, 6, 2, 3, 5, 1, 7 ]


main =
    div [ style [ ( "font-family", "monospace" ) ] ]
        [ display "depth deepTree" (depth deepTree)
        , display "depth niceTree" (depth niceTree)
        , display "incremented" (map (\n -> n + 1) niceTree)
        , display "sum deepTree" (sum deepTree)
        , display "sum niceTree" (sum niceTree)
        , display "fold sumByFold 0 deepTree" (fold sumByFold 0 deepTree)
        , display "fold sumByFold 0 niceTree" (fold sumByFold 0 niceTree)
        , display "sumUsingFold deepTree" (sumUsingFold deepTree)
        , display "sumUsingFold niceTree" (sumUsingFold niceTree)
        , display "flatten deepTree" (flatten deepTree)
        , display "flatten niceTree" (flatten niceTree)
        , display "fold flattenByFold deepTree" (fold flattenByFold [] deepTree)
        , display "fold flattenByFold niceTree" (fold flattenByFold [] niceTree)
        , display "flattenUsingFold deepTree" (flattenUsingFold deepTree)
        , display "flattenUsingFold niceTree" (flattenUsingFold niceTree)
        , display "isElement deepTree 3" (isElement 3 deepTree)
        , display "isElement deepTree 4" (isElement 4 deepTree)
        , display "isElement niceTree 3" (isElement 3 niceTree)
        , display "isElement niceTree 4" (isElement 4 niceTree)
        , display "isElementUsingFold 3 deepTree" (isElementUsingFold 3 deepTree)
        , display "isElementUsingFold 4 deepTree" (isElementUsingFold 4 deepTree)
        , display "isElementUsingFold 3 niceTree" (isElementUsingFold 3 niceTree)
        , display "isElementUsingFold 4 niceTree" (isElementUsingFold 4 niceTree)
        , display "fold countByFold 0 deepTree" (fold countByFold 0 deepTree)
        , display "fold countByFold 0 niceTree" (fold countByFold 0 niceTree)
        , display "preOrder deepTree" (preOrder deepTree)
        , display "preOrder niceTree" (preOrder niceTree)
        , display "inOrder deepTree" (inOrder deepTree)
        , display "inOrder niceTree" (inOrder niceTree)
        , display "postOrder deepTree" (postOrder deepTree)
        , display "postOrder niceTree" (postOrder niceTree)
        , display "levelOrder deepTree" (levelOrder deepTree)
        , display "levelOrder niceTree" (levelOrder niceTree)
        , br [] []
        , display "depth deepTree'" (depth deepTree')
        , display "depth niceTree'" (depth niceTree')
        , display "incremented" (map (\n -> n + 1) niceTree')
        , display "sum deepTree'" (sum deepTree')
        , display "sum niceTree'" (sum niceTree')
        , display "fold sumByFold 0 deepTree'" (fold sumByFold 0 deepTree')
        , display "fold sumByFold 0 niceTree'" (fold sumByFold 0 niceTree')
        , display "sumUsingFold deepTree'" (sumUsingFold deepTree')
        , display "sumUsingFold niceTree'" (sumUsingFold niceTree')
        , display "flatten deepTree'" (flatten deepTree')
        , display "flatten niceTree'" (flatten niceTree')
        , display "fold flattenByFold deepTree'" (fold flattenByFold [] deepTree')
        , display "fold flattenByFold niceTree'" (fold flattenByFold [] niceTree')
        , display "flattenUsingFold deepTree'" (flattenUsingFold deepTree')
        , display "flattenUsingFold niceTree'" (flattenUsingFold niceTree')
        , display "isElement deepTree' 3" (isElement 3 deepTree')
        , display "isElement deepTree' 4" (isElement 4 deepTree')
        , display "isElement niceTree' 3" (isElement 3 niceTree')
        , display "isElement niceTree' 4" (isElement 4 niceTree')
        , display "isElementUsingFold 3 deepTree'" (isElementUsingFold 3 deepTree')
        , display "isElementUsingFold 4 deepTree'" (isElementUsingFold 4 deepTree')
        , display "isElementUsingFold 3 niceTree'" (isElementUsingFold 3 niceTree')
        , display "isElementUsingFold 4 niceTree'" (isElementUsingFold 4 niceTree')
        , display "fold countByFold 0 deepTree'" (fold countByFold 0 deepTree')
        , display "fold countByFold 0 niceTree'" (fold countByFold 0 niceTree')
        , display "preOrder deepTree'" (preOrder deepTree')
        , display "preOrder niceTree'" (preOrder niceTree')
        , display "inOrder deepTree'" (inOrder deepTree')
        , display "inOrder niceTree'" (inOrder niceTree')
        , display "postOrder deepTree'" (postOrder deepTree')
        , display "postOrder niceTree'" (postOrder niceTree')
        , display "levelOrder deepTree'" (levelOrder deepTree')
        , display "levelOrder niceTree'" (levelOrder niceTree')
        ]


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



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

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

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

The output of the above is the following

depth deepTree ==> 3
depth niceTree ==> 2
incremented ==> Node 3 (Node 2 Empty Empty) (Node 4 Empty Empty)
sum deepTree ==> 6
sum niceTree ==> 6
fold sumByFold 0 deepTree ==> 6
fold sumByFold 0 niceTree ==> 6
sumUsingFold deepTree ==> 6
sumUsingFold niceTree ==> 6
flatten deepTree ==> [1,2,3]
flatten niceTree ==> [1,2,3]
fold flattenByFold deepTree ==> [1,2,3]
fold flattenByFold niceTree ==> [2,1,3]
flattenUsingFold deepTree ==> [1,2,3]
flattenUsingFold niceTree ==> [2,1,3]
isElement deepTree 3 ==> True
isElement deepTree 4 ==> False
isElement niceTree 3 ==> True
isElement niceTree 4 ==> False
isElementUsingFold 3 deepTree ==> True
isElementUsingFold 4 deepTree ==> False
isElementUsingFold 3 niceTree ==> True
isElementUsingFold 4 niceTree ==> False
fold countByFold 0 deepTree ==> 3
fold countByFold 0 niceTree ==> 3
preOrder deepTree ==> [1,2,3]
preOrder niceTree ==> [2,1,3]
inOrder deepTree ==> [1,2,3]
inOrder niceTree ==> [1,2,3]
postOrder deepTree ==> [3,2,1]
postOrder niceTree ==> [1,3,2]
levelOrder deepTree ==> [1,2,3]
levelOrder niceTree ==> [2,1,3]

depth deepTree' ==> 7
depth niceTree' ==> 3
incremented ==> Node 5 (Node 3 (Node 2 Empty Empty) (Node 4 Empty Empty)) (Node 7 (Node 6 Empty Empty) (Node 8 Empty Empty))
sum deepTree' ==> 28
sum niceTree' ==> 28
fold sumByFold 0 deepTree' ==> 28
fold sumByFold 0 niceTree' ==> 28
sumUsingFold deepTree' ==> 28
sumUsingFold niceTree' ==> 28
flatten deepTree' ==> [1,2,3,4,5,6,7]
flatten niceTree' ==> [1,2,3,4,5,6,7]
fold flattenByFold deepTree' ==> [1,2,3,4,5,6,7]
fold flattenByFold niceTree' ==> [4,2,1,3,6,5,7]
flattenUsingFold deepTree' ==> [1,2,3,4,5,6,7]
flattenUsingFold niceTree' ==> [4,2,1,3,6,5,7]
isElement deepTree' 3 ==> True
isElement deepTree' 4 ==> True
isElement niceTree' 3 ==> True
isElement niceTree' 4 ==> True
isElementUsingFold 3 deepTree' ==> True
isElementUsingFold 4 deepTree' ==> True
isElementUsingFold 3 niceTree' ==> True
isElementUsingFold 4 niceTree' ==> True
fold countByFold 0 deepTree' ==> 7
fold countByFold 0 niceTree' ==> 7
preOrder deepTree' ==> [1,2,3,4,5,6,7]
preOrder niceTree' ==> [4,2,1,3,6,5,7]
inOrder deepTree' ==> [1,2,3,4,5,6,7]
inOrder niceTree' ==> [1,2,3,4,5,6,7]
postOrder deepTree' ==> [7,6,5,4,3,2,1]
postOrder niceTree' ==> [1,3,2,5,7,6,4]
levelOrder deepTree' ==> [1,2,3,4,5,6,7]
levelOrder niceTree' ==> [4,2,6,1,3,5,7]

You can download the solution from here binary-tree.elm (compressed) (115 downloads)

Leave a Reply