[elm-discuss] Is it possible to write a general tree-fold function?

[Vlad GURDIGA]

Hi! 👋

I’m trying to get through the exercises in the Binary Tree example here:
http://elm-lang.org/examples/binary-tree.

I’ve got to the 4-th and it seems to me like it’s impossible to solve (with
the understanding I have now). 🀔

So, here it goes:

(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


and here is my attempt to solve it:

fold : (a -> b -> b) -> b -> Tree a -> b

fold f z tree =
case tree of
Empty ->

z
Node v left right ->

let
z_ = f v z
l_ = fold f z left
r_ = fold f z right
in
{- TODO: figure out how to combine the 3 values of type b -}
f v z_

The issue I’m stuck with in the last case —​ Node v left right -> — is that
I now got 3 values of type b which I can’t fold into the final result: f has
the type of (a -> b -> b), so if the only value of type a here is z, the
most I can do is one folding operation, but I get another b as a result. 😶

My question is: How can I fold the 3 values? Or is this approach workable
at all? What am I missing? 🀔

Cheers! 👋

[Peter Damoc]

Hi Vlad,

So, the hint is that the folding function takes as the second parameter a
`b` and the output of fold is a `b`

If that isn't enough, think about the fact that `right` and `left` are
`Tree a` and that fold takes a `Tree a`

Also, you are not given a function that takes two `b` and produces another
`b` ;)

And finally, the last hint: you don't need a `let` (you could use one but
you don't have to) ;)

...
|> ...
|> ...

Post by Vlad GURDIGA
Hi! 👋
http://elm-lang.org/examples/binary-tree.
I’ve got to the 4-th and it seems to me like it’s impossible to solve
(with the understanding I have now). 🀔
(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

fold : (a -> b -> b) -> b -> Tree a -> b

fold f z tree =
case tree of
Empty ->

z
Node v left right ->

let
z_ = f v z
l_ = fold f z left
r_ = fold f z right
in
{- TODO: figure out how to combine the 3 values of type b -}
f v z_

The issue I’m stuck with in the last case —​ Node v left right -> — is
that I now got 3 values of type b which I can’t fold into the final
result: f has the type of (a -> b -> b), so if the only value of type a here
is z, the most I can do is one folding operation, but I get another b as
a result. 😶
My question is: How can I fold the 3 values? Or is this approach workable
at all? What am I missing? 🀔
Cheers! 👋
--
You received this message because you are subscribed to the Google Groups
"Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an
For more options, visit https://groups.google.com/d/optout.

[Max Goldstein]

I will add that you are using z when you define _l and _r but you only need to use it once.

Also, a good test case is to write an in-order traversal on a binary search tree that will return the keys in sorted order.