{{ message }}

Instantly share code, notes, and snippets.

# kuanyingchou/elm-binary-tree.elm

Created Nov 20, 2015
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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]

### avinashcodes commented Apr 2, 2016

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