Follow

There was a post pointing to the beautiful more than 30 years old paper "Why Functional Programming Matters" John Hughes. I could not find the post again to reply,

The paper gives a definition of "foldtree" on page 7:
"
foldtree f g a (Node label subtrees) =
f label (foldtree f g a subtrees)
foldtree f g a (Cons subtree rest) =
g (foldtree f g a subtree) (foldtree f g a rest)
foldtree f g a Nil = a
"

I wonder what the type of "foldtree" could be. Since the last argument
is "treeof ∗" in the first declaration but "(listof (treeof ∗)" in the second.

In I would implement it as:

data Tree a = Node a [Tree a]

foldtree :: (a -> b -> b) -> (b -> b -> b) -> b -> Tree a -> b
foldtree f g a (Node x []) = f x a
foldtree f g a (Node x (t:ts)) =
g (foldtree f g a t) (foldtree f g a (Node x ts))

But probably I'm miss something here, since it takes only two declarations.

@mdrslmr In the version of the paper I have, there are two mutually recursive functions `redtree` and `redtree'` being defined, which converted to Haskell syntax and with explicit type signatures look as follows:
```
redtree :: (x -> l -> t) -> (t -> l -> l) -> l -> Tree x -> t
redtree f g a (Node label subtrees) =
f label (redtree' f g a subtrees)

redtree' :: (x -> l -> t) -> (t -> l -> l) -> l -> [Tree x] -> l
redtree' f g a (subtree : rest) =
g (redtree f g a subtree) (redtree' f g a rest)
redtree' f g a [] =
a
```

@kosmikus
I didn't know there where different versions of the paper. Cool, yes this way the types of the functiobs are uniquely defined Thanks.

@mdrslmr I think this paper has been re-typeset and republished a number of times. Perhaps some revisions have fixed or introduced typos ...

@kosmikus
Your solution is much better than mine.
It dose not need to construct tree (nodes) and it does not reorder the nodes if doing something like this:
"
rlisttree :: Tree a -> [a]
rlisttree = redtree (:) (++) []
"

@mdrslmr It's not my solution. It's the solution by John Hughes. But yes, it is better.

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.