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.
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
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 (:) (++) []
"
Add comment