sorting - 理解 Haskell 中的树排序问题

Question

我试图弄清楚 here 中的树排序到底是如何进行的工作(我理解展平、插入和折叠)。

我想树排序中所做的是对列表上的每个元素应用插入，从而生成一棵树，然后将其展平。我在这里无法克服的唯一问题是列表(即函数的参数)隐藏在哪里(因为除了函数类型声明之外，它没有作为参数写入任何地方)。

还有一件事:既然点运算符是函数组合，为什么当我更改时会出现错误: treesort = flatten 。 foldr insert Leaf 到 treesort = flatten(foldr insert Leaf )?

Answer 1

what's being done in treesort is applying insert for each element on the list thus generating a tree and then flattening it.

完全正确。

[Where is the list hiding?]

在函数式语言中，您不必给出函数类型值的参数。例如，如果我写

f = concat . map (map toUpper) 

我得到一个类型为[[Char]] -> [Char]的函数。这 即使定义方程中没有参数，函数也需要一个参数。 它完全和我写的一样

f strings = (concat . map (map toUpper)) strings

Since the dot operator is function composition, why is it wrong to change f . g to f (g)?

它们的意思不同。当每个都应用于x时会发生什么？

(f . g) x  = f (g x)

(f (g)) x  = (f g) x

您可以看到应用程序以不同的方式关联，并且f。 g 与 f g 不同。

这是一个类型错误，因为 foldr insert Leaf 是一个从列表到树的函数，而 flatten 旨在应用于单个树，而不是函数。