Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment