在树上的haskell折叠操作

Question

data Tree a = Tree a [Tree a]

请注意,我们不允许空树,并且叶子是具有空子列表的树.

treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f (Tree x s) = f x (map (treeFold f) s)

鉴于上述信息,我不明白树折叠函数如何通过递归地将折叠操作应用于子树,然后将函数应用于根处的标签以及从子树返回的结果来返回结果.

我也没有得到树Fold函数如何只接受一个参数而不是2,当它作为参数传递给map函数并且它仍然编译并正确运行时.

例如,下面的树大小函数计算树的节点.

treeSize :: Tree a -> Int
treeSize = treeFold (\x ys -> 1 + sum ys)

因此运行treeSize树,其中树tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]的大小为4.

在上面的树大小函数中,树折函数也传递一个参数而不是两个.另外,传递给树折函数的x并没有在任何地方使用,所以为什么你需要它.删除它会导致程序无法编译,并提供以下错误消息.

 Couldn't match type `a' with `[[Int] -> Int]'
      `a' is a rigid type variable bound by
          the type signature for treeSize :: Tree a -> Int
          at treeFold.hs:15:1
    In the first argument of `sum', namely `ys'
    In the second argument of `(+)', namely `sum ys'
    In the expression: 1 + sum ys

任何帮助将不胜感激.

Answer 1

未使用的参数

首先,将变量显式标记为未使用的方式是将变量替换为_.所以你真的想要:

treeFold (\_ ys -> 1 + sum ys)

您遇到编译器错误,因为您写道:

treeFold (\ys -> 1 + sum ys)

......这不是一回事.

褶皱

其次,我将treeSize在一个示例树上进行评估,以便您可以看到没有任何魔法:

treeSize (Tree 1 [Tree 2 [], Tree 3 []])

-- Inline definition of 'treeSize'
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []])

-- Evaluate treeFold
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])

-- Apply the anonymous function
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])

-- Apply the 'map' function
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 [])
          , treeFold (\_ ys -> 1 + sum ys) (Tree 3 [])
          ]

-- Apply both 'treeFold' functions
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) [])
          , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) [])
          ]

-- Apply the anonymous functions
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
          , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
          ]

-- map f [] = []
= 1 + sum [ 1 + sum []
          , 1 + sum []
          ]

-- sum [] = 0
= 1 + sum [1 + 0, 1 + 0]
= 1 + sum [1, 1]

-- Apply 'sum'
= 1 + 2
= 3

但是,有一种简单的方法可以记住它是如何treeFold工作的.它只是Tree用你提供的函数替换每个构造函数.

所以如果你有:

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]]

...并且您申请treeFold f,它将评估为:

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]]

treeSum只是特殊情况f = (\_ ys -> 1 + sum ys):

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]]

= 7

哗众取宠

最后一点是如何在Haskell中进行调整.定义如下函数时:

foo x y = x + y

...编译器实际上将它解释为两个嵌套函数:

foo = \x -> (\y -> x + y)

这就是为什么你可以将函数部分应用于Haskell中的一个参数.当你写作时foo 1,它转换为:

foo 1

= (\x -> (\y -> x + y)) 1

= \y -> 1 + y

换句话说,它返回一个参数的新函数.

在Haskell中,所有函数只接受一个参数,并通过返回新函数来模拟多个参数的函数.这种技术被称为"currying".

如果您更喜欢更传统的主流语言的多参数方法,可以通过让函数接受一个元组参数来模拟它:

f (x, y) = x + y

但是,这不是真正惯用的Haskell,它不会给你任何性能提升.

Answer 2

第一个问题有点棘手，因为这就是递归的问题......正如老师所说：“要理解递归，你必须学习递归是如何工作的”。:-P 一个小建议：尝试使用一棵树或一棵树内部包含一棵树来进行应用treeFold，并自行评估（在论文等上）。我想，然后你可以感觉到正在发生的事情......（当然使用一个简单的函数作为 treeFold 的参数；就像你的 treeSize 使用的那样）。

treeFold在映射主体中仅获取一个参数，因为map需要一个来自 的函数a->b，并且treeFold具有类型(a -> [b] -> b) -> Tree a -> b.，因此如果您向其传递 2 个参数，则将map仅传递给一个值，这会导致失败。（一个可以理解的例子： (+) 需要两个参数。如果你写，map (+1) [1,2,3]你会得到[2,3,4] ，因为 (+1) 应用于列表中的每个元素（并且 (+1) 显然还需要一个参数，如上面所示treeFold f）

你的例子 treeSize ：当你说它只得到一个参数时，这是不对的。你可以写

treeSize t = treeFold (\x ys -> 1 + sum ys) t

而不是你上面的定义。不使用 x，因为对于计数来说它是无用的。但是，treeFold 需要有一个函数，它需要两个参数，所以你给它 x。这是唯一的原因。您可以传递任何其他值。