How about John Hughes' folding ", I don’t understand?

Question

John Hughes, in his famous article entitled Why functional programming issues , describes data types for lists and ordered marked trees,

listof * ::= Nil | Cons * (listof *) treeof * ::= Node * (listof (treeof *)) 

and a function called foldtree ,

 foldtree fga (Node label subtrees) = f label (foldtree fga subtrees) foldtree fga (Cons subtree rest) = g (foldtree fga subtree) (foldtree fga rest) foldtree fga Nil = a 

I implemented these two data types in Haskell, and I'm currently trying to implement foldtree ,

 data Listof a = Nil | Cons a (Listof a) deriving (Read, Show, Eq) -- implementation of some list functions... (skipped) data Treeof a = Node a (Listof (Treeof a)) deriving (Read, Show, Eq) foldtree fga (Node label subtrees) = f label (foldtree fga subtrees) foldtree fga (Cons subtree rest) = g (foldtree fga subtree) (foldtree fga rest) foldtree fga Nil = a 

but I get type mismatches:

 Couldn't match expected type 'Treeof t' with actual type 'Listof (Treeof t)' Relevant bindings include subtrees :: Listof (Treeof t) (bound at whyFunMatters.hs:27:28) label :: t (bound at whyFunMatters.hs:27:22) f :: t -> t1 -> t1 (bound at whyFunMatters.hs:27:10) foldtree :: (t -> t1 -> t1) -> (t1 -> t1 -> t1) -> t1 -> Treeof t -> t1 (bound at whyFunMatters.hs:27:1) In the fourth argument of 'foldtree', namely 'subtrees' In the second argument of 'f', namely '(foldtree fga subtrees)' 

(etc.).

After thinking a little more about the implementation of the Hughes (pseudo) foldtree , I'm not sure that I understand this, and these type mismatches seem obvious to me. More specifically, the foldtree type of the fourth argument does not seem consistent across three patterns:

• in the first template, this argument is of type Treeof a , whereas
• in the last two templates it is of type Listof (Treeof a) .

What am I missing?

Answer 1

The correct definition should consist of a pair of mutually recursive functions, one for folding trees and one for folded forests (tree lists):

 foldtree :: (a -> c -> b) -> (b -> c -> c) -> c -> Treeof a -> b foldtree fga (Node label subtrees) = f label (foldforest fga subtrees) foldforest :: (a -> c -> b) -> (b -> c -> c) -> c -> Listof (Treeof a) -> c foldforest fga (Cons subtree rest) = g (foldtree fga subtree) (foldforest fga rest) foldforest fga Nil = a 

I think that the author mistakenly combined two different (but closely related) functions together. I suspect that the author did not actually write Haskell, but rather a pseudo-code similar to Haskell, so the code was simply used to present the algorithm in an unofficial way.

Please note that the document apparently assumes that it is Miranda, the predecessor of Haskell, but I cannot confirm if this is Miranda's legal code.

Answer 2

Rufflewind's answer is the most obvious way to correct a dubious foldtree definition from Hughes' famous article. However, there is a much more concise and modular solution that requires only one line of code and reuse of foldr . Scroll to the end of this message to see this definition. Read on for some definition definition.

Compare the definition of Rufflewind foldforest :

 foldforest fga (Cons subtree rest) = g (foldtree fga subtree) (foldforest fga rest) foldforest fga Nil = a 

... with Hughes (slightly modified) definition of foldr from the article:

 foldr fa (Cons e rest) = fe (foldr fa rest) foldr fa Nil = a 

Do they both look terribly similar? In fact, the only difference is that in foldforest we apply foldtree fga to subtree and (through recursion) to all the other elements in the list of subtrees before we "merge" them with g . Is it possible to define an operator that does this and can be passed to foldr ?

foldforest out the foldforest kernel, where the actual work is done: g (foldtree fga subtree) . Using the functional composition (defined in the work of Hughes as (f . g) h = f (gh) ), we can express this part in different ways:

 foldforest fga (Cons subtree rest) = (g . foldtree fga) subtree (foldforest fga rest) 

Now let's define h = (g . foldtree fga) for brevity and pass the specific list of subtrees to foldforest , foldforest the recursion using our new notation:

 foldforest fga (Cons subtree1 (Cons subtree2 Nil)) = h subtree1 (h subtree2 a) 

What does a recursion deployment of a similar call to foldr look like?

 foldr fa (Cons subtree1 (Cons subtree2 Nil)) = f subtree1 (f subtree2 a) 

Now it’s obvious that we managed to extract the operator from foldforest , which we can pass to foldr along with the start state a and the list Treeof s. A complete foldtree definition that maximizes modularity and conciseness should be:

 foldtree fga (Node label subtrees) = f label (foldr (g . foldtree fga) a subtrees) 

Answer 3

In a Google search, I found the link https://gist.github.com/vu3rdd/14f10df24fbeffda09ae, where the author reports that the document has been updated and is available at http://www.cse.chalmers.se/~rjmh/Papers. /whyfp.pdf .

Author John Hughes even apologizes for examples not found on haskell!

This article dates from 1984 and has been distributed for many years as a Chalmers memorandum. Slightly revised versions appeared in 1989 and 1990 as [Hug90] and [Hug89]. This version is based on the original source of the Chalmers memo, slightly edited for LaTeX and brings it closer to published versions, with one or two bug fixes. Please excuse the slightly old-fashioned typing and the fact that the examples are not in Haskell!

The following are corrections submitted by the author ...

 redtree fga (node label subtrees) = f label (redtree fga subtrees) redtree fga (cons subtree rest) = g (redtree fga subtree) (redtree fga rest) redtree fga nil = a