There was a post pointing to the beautiful more than 30 years old #functionalprogramming 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 #haskell 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.
@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.
@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
```