我误解了 John Hughes 的“foldtree”吗？

Question

John Hughes 在他题为 Why Functional Programming Matters 的著名文章中描述了列表和有序标记树的数据类型、

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

（等等）

在进一步思考 foldtree 的 Hughes（伪）实现之后，我不太确定我是否理解它，那些类型不匹配现在对我来说似乎很明显。更具体地说，foldtree 的第四个参数的类型在三个模式中似乎并不一致：

在第一个模式中，该参数的类型为 Treeof a，而
在最后两个模式中，它的类型是Listof (Treeof a)。

我错过了什么？

Answer 1

一个正确的定义应该由一对相互递归的函数组成，一个用于折叠 trees，一个用于折叠 forests（列表树）：

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

Answer 2

Rufflewind 的回答是解决 Hughes 著名论文中 foldtree 的有问题定义的最明显方法。然而，有一个更简洁和模块化的解决方案，只需要一行代码并重用 foldr。滚动到此 post 的底部以查看此定义。继续阅读定义的某种推导。

比较 Rufflewind 对 foldforest 的定义：

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

...休斯（略有改动）对论文中 foldr 的定义：

foldr f a (Cons e rest)              = f e (foldr f a rest)
foldr f a Nil                        = a

他们看起来是不是非常相似？事实上，唯一的区别是，在 foldforest 中，我们将 foldtree f g a 应用于 subtree 并（通过递归）应用于 "merging" 之前的子树列表中的所有其他元素 g。我们可以定义一个运算符来执行此操作并可以传递给 foldr?

让我们仔细看看 foldforest 的核心，实际工作完成的地方：g (foldtree f g a subtree)。使用函数组合（在 Hughes 的论文中定义为 (f . g) h = f (g h)）我们可以用不同的方式表达这部分：

foldforest f g a (Cons subtree rest) = (g . foldtree f g a) subtree (foldforest f g a rest)

现在让我们为简洁起见定义 h = (g . foldtree f g a) 并将具体的子树列表传递给 foldforest 使用我们的新符号展开递归：

foldforest f g a (Cons subtree1 (Cons subtree2 Nil)) 
                                     = h subtree1 (h subtree2 a)

展开对 foldr 的类似调用的递归是什么样子的？

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

现在很明显，我们能够从 foldforest 中提取一个运算符，我们可以将其与起始状态 a 和 [=34 的列表一起传递给 foldr =]秒。 foldtree 的完整定义，最大化模块化和简洁性，因此应该是：

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

Answer 3

在 Google 上搜索我找到了 link https://gist.github.com/vu3rdd/14f10df24fbeffda09ae where the author informs that the document has been updated and is available at http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf。

作者 John Hughes 甚至为没有出现在 haskell!

上的例子道歉

This paper dates from 1984, and circulated as a Chalmers memo for many years. Slightly revised versions appeared in 1989 and 1990 as [Hug90] and [Hug89]. This version is based on the original Chalmers memo nroff source, lightly edited for LaTeX and to bring it closer to the published versions, and with one or two errors corrected. Please excuse the slightly oldfashioned type-setting, and the fact that the examples are not in Haskell!

下面作者给出的更正...

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

我误解了 John Hughes 的“foldtree”吗？

What about John Hughes' `foldtree` am I misunderstanding?

haskell

fold

type-mismatch

algebraic-data-types