Is there a type-mismatch mistake in John Hughes's definition of foldtree?

Question

John Hughes, in his famous article entitled Why Functional Programming Matters, describes data types for lists and ordered labelled trees,

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

and a function called foldtree,

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've implemented those 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 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

but I'm getting 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 f g a subtrees)’

(etc.)

After thinking some more about Hughes (pseudo)implementation of foldtree, I'm not so sure I understand it, and those type mismatches now seem obvious to me. More specifically, the type of foldtree's fourth argument doesn't seem consistent across the three patterns:

• in the first pattern, that argument has type Treeof a, whereas
• in the last two patterns, it has type Listof (Treeof a).

What am I missing?

Answer 1

A proper definition should consist of a pair of mutually recursive functions, one for folding trees and one for folding forests (lists of trees):

foldtree :: (a -> c -> b) -> (b -> c -> c) -> c -> Treeof a -> b
foldtree f g a (Node label subtrees) = f label (foldforest f g a subtrees)

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

I think the author has mistakenly combined two different (but closely related) functions together. I suspect what the author wrote is not really Haskell but more of a Haskell-like pseudocode, so the code was just used to present the algorithm in an informal way.

Note that the paper seems to suggest it's Miranda, a predecessor of Haskell, but I can't confirm if this is legal Miranda code either.