Implementation of Binary Search Tree in Elm

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


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


main : Element
main =
    flow down
        [ display "depth" depth t1
        , display "depth" depth t2
        , display "map ((+)1)" (map ((+)1)) t2
        , display "sum" sum t2
        , display "flatten" flatten t2
        , display "isElement" (isElement 7) t2
        , display "sum with fold" (fold (+) 0) t2
        , display "flatten with fold" (fold (::) []) t2
        --, display "isElement with fold" (fold ((==) >> (||)) False) t2
        , display "map with fold" (map' ((+)1)) t2
        , display "depth with fold" depth' t2
        ]

map' : (a -> comparable) -> Tree a -> Tree comparable
map' f tree = fold (\x xs -> insert (f x) xs) empty tree

depth' : Tree a -> Int
depth' = fold (\x n -> 1 + n) 0

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 x left right ->
        x + sum left + sum right

flatten : Tree a -> List a
flatten tree =
  case tree of
    Empty -> []
    Node x left right ->
     flatten left ++ [x] ++ flatten right

isElement : comparable -> Tree comparable -> Bool
isElement a tree =
  case tree of
    Empty -> False
    Node x left right -> 
      if x == a then
        True
      else if a > x then
        isElement a right
      else
        isElement a left
        

fold : (a -> b -> b) -> b -> Tree a -> b
fold fn base tree =
  let
    xs = flatten tree
    fold' f v ys =
      case ys of
      [] -> base
      (y::ys) -> f y (fold' f v ys)
  in
    fold' fn base xs
    

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


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

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

Hi,
I've started learning elm recently mostly by reading docs and going through examples.

When I am attempting to solve binary tree challenges here http://elm-lang.org/examples/binary-tree , I am getting some weird errors. I thought I was doing something wrong.

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


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


main : Element
main =
    flow down
        [ display "depth" depth t1
        , display "depth" depth t2
        , display "map ((+)1)" (map ((+)1)) t2
        , display "sum" sum t1
        , display "Flatten" flatten t1
        , display "Flatten with fold" flatten' t1
        , display "isElement" (isElement 4) t1
        , display "isElement" (isElement 1) t1
        ]

I am running into two issues

• When compiling I am getting the following error

The type annotation for `fold` does not match its definition.
fold : (a -> b -> b) -> b -> Tree a -> b
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The type annotation is saying:

    (a -> b -> b) -> b -> Tree a -> b

But I am inferring that the definition has this type:

    (a -> a -> a) -> a -> Tree a -> a

• When I changed the type annotation to the inferred definition, I am getting a different error

The type annotation for `flatten'` does not match its definition.

102│ flatten' : Tree a -> List a
                ^^^^^^^^^^^^^^^^
The type annotation is saying:

    Tree a -> List a

But I am inferring that the definition has this type:

    Tree (List ∞) -> List ∞

I am using Elm-make version 0.16 in my PC, running the code in my PC and on online editor gives me the same errors.

However I am perfectly able to run your code. The only difference I see is in your fold function you are flattening the tree to a list and folding over the list instead of folding over the tree directly.

Is it the only way to do it? Why cant I directly fold over the tree?

Sorry for the long comment.

Thank you

@avinashsmiles, the following comes without testing, but consider:
your code: fold f (fold f (f b n) left) right
should be: fold f (fold f (f n b) left) right