约翰休斯的"折叠树"怎么样？我误解了吗？

Question

John Hughes在题为" 为什么功能编程重要"的着名文章中描述了列表和有序标记树的数据类型,

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

和一个函数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

我在Haskell中实现了这两种数据类型,我目前正在尝试实现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

但我得到类型不匹配:

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)’

(等等.)

在考虑了更多关于Hughes(伪)实现之后foldtree,我不太确定我理解它,那些类型不匹配现在对我来说显而易见.更具体地说,foldtree第四个参数的类型在三种模式中似乎不一致:

• 在第一种模式中,该参数具有类型Treeof a,而
• 在最后两种模式中,它有类型Listof (Treeof a).

我错过了什么？

Answer 1

一个正确的定义应该由一对相互递归的函数组成,一个用于折叠树,另一个用于折叠森林(树木列表):

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

我认为作者错误地将两个不同(但密切相关)的函数组合在一起.我怀疑作者写的不是真正的Haskell,而是更像是类似Haskell的伪代码,所以代码只是用来以非正式的方式呈现算法.

请注意,该论文似乎暗示它是Haskell的前身Miranda,但我无法确认这是否是合法的Miranda代码.