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) (430 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) (430 downloads)