BinaryTree.elm

import Graphics.Element exposing (..)
import Text


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

-- declaring type of function named `empty`
empty : Tree a
-- defining function named `empty` and implementing it by returning `Empty`
empty =
    Empty


-- declaring type of function `singleton` as creating a tree with 
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)


square: Int -> Int
square x = x * x

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


main : Element
main =
  flow down
        [ display "depth" depth empty
        , display "depth" depth t1
        , display "depth" depth t2
        , display "map ((+)1)" (map ((+)1)) t2
        , display "map (square)" sum ((map (square)) t2)
        , show (flatten ((map (square)) t2))
        , show (isElement 8 t1)
        , show (isElement 1 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


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


flatten : Tree item -> List item
flatten tree = 
    case tree of 
        Empty -> []
        Node v left right -> 
            (flatten left) ++ [v] ++ (flatten right)

isElement : a -> Tree a -> Bool
isElement a tree =
    case tree of
        Empty -> False
        Node v left right ->
            v == a || (isElement a left) || (isElement a right) 

--fold : (a -> b -> b) -> b -> Tree a -> b
--the following fold is instead of what is above. haven't got the fix
--yet
fold : (a -> a -> a) -> a -> Tree a -> a
fold f base tree = 
    case tree of
        Empty -> base
        Node v left right ->
            f (f v (fold f base left)) (fold f base right)