elm-binary-tree.elm

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

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

isElement : a -> Tree a -> Bool
isElement e tree =
    case tree of 
      Empty -> False
      
      Node v left right -> 
          if e == v then
              True
          else
              (isElement e left) || (isElement e right)
       
fold : (a -> b -> b) -> b -> Tree a -> b
fold f a tree =
    case tree of
      Empty -> a
      
      Node v left right -> 
          fold f (fold f (f v a) left) right

sum' : Tree Int -> Int
sum' tree = fold (+) 0 tree

flatten' : Tree a -> List a
flatten' tree = fold (::) [] tree
  
isElement' : a -> Tree a -> Bool
isElement' t tree = 
    fold (\x y -> (x==t) || y) False tree

preorder : Tree a -> List a
preorder tree =
    case tree of
      Empty -> []

      Node v left right -> 
          [v] ++ preorder left ++ preorder right

inorder : Tree a -> List a
inorder tree =
    case tree of
      Empty -> []

      Node v left right -> 
          preorder left ++ [v] ++ preorder right

postorder : Tree a -> List a
postorder tree =
    case tree of
      Empty -> []

      Node v left right -> 
          preorder left ++ preorder right ++ [v]

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. But I am doing similar to your code here.

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 [4,2,3]
t2 = fromList [2,1,3]

sum : Tree Int -> Int
sum =
    fold (+) 0


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


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


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
        ]


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

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 if I use the code posted here https://gist.github.com/cskksc/3e3c40195b9ada88adb7 . I am able to run the code without any errors.

He is flattening the tree to a list and folding over the list instead of folding over the tree.

Is it the only way to do it? Can you provide me some insights into this why this is happening with our code?

Sorry for the long comment.

Thank you