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 ( [download id=”1828″]).
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 [download id=”1828″]
