理解 Haskell 中的树排序问题
我试图弄清楚 这里 的树排序究竟是如何工作的(我理解展平、插入和文件夹)。
我想树排序中所做的就是对列表上的每个元素应用插入,从而生成一棵树,然后将其展平。我在这里无法克服的唯一问题是列表(即函数的参数)隐藏在哪里(因为除了函数类型声明之外,它没有作为参数写入任何地方)。
还有一件事:既然点运算符是函数组合,为什么当我更改时会出现错误: treesort = flatten 。 foldr insert Leaf
到 treesort = flatten(foldr insert Leaf )
?
I am trying to figure out how exactly does treesort from here work (I understand flatten, insert and foldr).
I suppose what's being done in treesort is applying insert for each element on the list thus generating a tree and then flattening it. The only problem I can't overcome here is where the list (that is the argument of the function) is hiding (because it is not written anywhere as an argument except for the function type declaration).
One more thing: since dot operator is function composition, why is it an error when I change: treesort = flatten . foldr insert Leaf
to treesort = flatten( foldr insert Leaf )
?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
完全正确。
在函数式语言中,您不必给出函数类型值的参数。例如,如果我写,
我会得到一个
[[Char]] -> 类型的函数[字符]
。这即使定义方程中没有参数,函数也需要一个参数。
它完全就像我写的一样
它们的意思不同。当每个都应用于 x 时会发生什么?
您可以看到应用程序以不同的方式关联,并且
f。 g
与f g
不同。这是一个类型错误,因为
foldr insert Leaf
是从列表到树的函数,而flatten
旨在应用于单个树,而不是函数。Exactly right.
In a functional language, you don't have to give the arguments of a value of function type. For example if I write
I get a function of type
[[Char]] -> [Char]
. Thisfunction expects an argument even though there's no argument in the defining equation.
It's exactly the same as if I had written
They don't mean the same thing. What happens when each is applied to
x
?You can see the applications associate differently, and
f. g
is different fromf g
.It's a type error because
foldr insert Leaf
is a function from lists to trees, andflatten
is meant to be applied to a single tree, not to a function.首先要回答你的最后一个问题,你会收到一个错误,因为
.
是一个函数组合运算符,它需要两个函数(在本例中flatten
和foldr insert Leaf )。如果您想在不使用
.
的情况下重写代码,则需要创建一个带有某些参数的函数:这也解释了
list
参数隐藏的位置。编写函数时,不需要显式编写参数,因为表达式f 的结果。 g
是一个函数,它接受一些参数,调用g
然后调用f
:To answer your last question first, you're getting an error because
.
is a function composition operator that takes two functions (in this caseflatten
andfoldr insert Leaf
). If you want to rewrite the code without the use of.
, you'll need to create a function that takes some parameter:This also explains where the
list
parameter was hiding. When composing functions, you don't need to write parameters explicitly, because the result of the expressionf . g
is a function that takes some parameter, callsg
and then callsf
:有时,只要您不熟悉无意义的风格,在心里进行 epsilon 转换就会很有用。
如果 f 是函数类型的表达式,则可以将其转换为
\e-> (f) e
并且,如果我们有一个像这样的定义,
我们总是可以安全地将其重写为
因此
与
Sometimes, as long as you are not familiar with the pointless style, it is useful to do epsilon-conversion mentally.
If f is an expression with function type, then one can convert it to
\e -> (f) e
And, if we have a definition like
we can always safely rewrite it as
Thus
is the same as