bst_challenge.elm

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

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 Graphics.Element exposing (..)
import Text


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


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



main : Element
main =
    flow down
        [ display "depth" depth t1
        , display "depth" depth t2
        , display "map ((+)1)" (map ((+)1)) t2
        , display "sum t1" sum t1
        , display "flatten t1" flatten t1
        , display "fold t1" ( fold ( \a b -> a + b ) 0 ) t1
        , display "isElement t1 4" ( isElement 4 ) t1
        , display "isElement t1 2" ( isElement 2 ) t1
        , display "aSum t1" aSum t1
        , display "aFlatten t1" aFlatten t1
        , display "aIsElement t1" (aIsElement 2) t1
        ]

 

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



-- (1) Sum all of the elements of a tree.
sum : Tree Int -> Int
sum tree =
  case tree of
    Empty ->
        0
    
    Node v left right ->
      v + ( sum left ) + ( sum right )


-- (2) Flatten a tree into a list.
flatten : Tree a -> List a
flatten tree =
  case tree of
    Empty ->
        []
    
    Node v left right ->
        v :: ( List.append ( flatten left ) ( flatten right ) )


-- (3) Check to see if an element is in a given tree.
isElement : a -> Tree a -> Bool
isElement x tree =
  case tree of
    Empty ->
      False
    
    Node y left right ->
      y == x || ( isElement x left ) || ( isElement x right )


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


-- (5) Use "fold" to do exercises 1-3 in one line each.
aSum : Tree Int -> Int
aSum tree =
  fold (\a b -> a + b) 0 tree
  

aFlatten : Tree a -> List a
aFlatten tree =
  fold (\a b -> a :: b) [] tree

aIsElement : a -> Tree a -> Bool
aIsElement x xt =
  fold (\a b -> b || a == x) False xt


-- (6) Can "fold" be used to implement "map" or "depth"?