haskell - 我误会了约翰·休斯(John Hughes)的 `foldtree`呢？

约翰·休斯(John Hughes)在他的著名文章Why Functional Programming Matters中描述了列表和有序标签树的数据类型，



还有一个叫做foldtree的函数，



我已经在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)’

(等等。)

在考虑了更多关于foldtree的Hughes(伪)实现之后，我不太确定自己是否理解它，这些类型的不匹配现在对我来说很明显。更具体地说，foldtree的第四个参数的类型在以下三种模式中似乎不一致:

在第一个模式中为

，该参数的类型为Treeof a，而

在最后两种模式中，

的类型为Listof (Treeof a)。

我想念什么？

最佳答案

适当的定义应包括一对相互递归的函数，一个用于折叠树，一个用于折叠森林(树列表):

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代码。

关于haskell - 我误会了约翰·休斯(John Hughes)的 `foldtree`呢？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27928290/