带有 foldr 的 Haskell 递归函数示例

Question

在短暂的中断之后，我再次开始学习 Haskell，我目前正试图更好地理解递归和 lambda 表达式在 Haskell 中的工作原理。

在此:YouTube video ，就其实际工作方式而言，有一个函数示例让我感到困惑的程度远远超过它可能应该的:

firstThat :: (a -> Bool) -> a -> [a] -> a
firstThat f = foldr (\x acc -> if f x then x else acc)

为了清楚起见并且因为它对我来说不是很明显，我将给出一个将这个函数应用于一些参数的例子:

firstThat (>10) 2000 [10,20,30,40] --returns 20, but would return 2000, if none of the values in the list were greater than 10

如果我的假设是错误的，请纠正我。

看来 firstThat接受三个参数:

一个接受一个参数并返回一个 bool 值的函数。由于>运算符实际上是一个中缀函数，上例中的第一个参数似乎是对 > 的部分应用的结果。功能 - 这是正确的吗？

与作为第一个参数提供的函数的缺失参数相同类型的未指定值

上述类型的值列表

但实际功能 firstThat似乎与其类型声明的定义不同，只有一个参数。由于 foldr通常需要三个参数，我收集到有某种部分应用正在发生。作为参数提供给 foldr 的 lambda 表达式似乎也错过了它的论点。

那么，这个功能究竟是如何工作的呢？如果我太稠密或只见树木不见森林，我深表歉意，但我就是无法绕开它，这令人沮丧。

任何有用的解释或示例将不胜感激。

谢谢!

Answer 1

But the actual function firstThat seems to be defined differently from its type declaration, with just one argument. Since foldr normally takes three arguments I gathered there is some kind of partial application happening.

你说的对。然而，有一种比谈论“缺失的论点”更好的表达方式——这种方式不会让你问他们到哪里去了。以下是不缺少论点的两种方式。

首先，考虑这个函数:

add :: Num a => a -> a -> a
add x y = x + y

你可能知道，我们也可以这样定义它:

add :: Num a => a -> a -> a
add = (+)

这是有效的，因为 Haskell 函数和其他函数一样是值。我们可以简单地定义一个值， add ，等于另一个值， (+) ，这恰好是一个函数。声明函数不需要特殊语法。结果是(几乎)不需要显式编写参数。我们这样做的主要原因是因为它通常使代码更具可读性(例如，我可以定义 firstThat 而不显式编写 f 参数，但我不会这样做，因为结果相当可怕)。

其次，每当您看到具有三个参数的函数类型时...

firstThat :: (a -> Bool) -> a -> [a] -> a

……你也可以这样读……

firstThat :: (a -> Bool) -> (a -> [a] -> a)

...也就是说，一个参数的函数产生两个参数的函数。这适用于多个参数的所有函数。关键的一点是，从本质上讲，所有 Haskell 函数都只接受一个参数。这就是部分应用有效的原因。所以一看到...

firstThat :: (a -> Bool) -> a -> [a] -> a
firstThat f = foldr (\x acc -> if f x then x else acc)

...你可以准确地说你已经明确地写了 firstThat的所有参数。需要——也就是说，只有一个:)

The lambda expression provided as an argument to foldr seem to be missing its arguments too.

并不真地。 foldr (当仅限于列表时)是......

foldr :: (a -> b -> b) -> b -> [a] -> b

...因此传递给它的函数需要两个参数(鉴于上面的讨论，请随意在“两个”周围添加引号)。 lambda被写成...

\x acc -> if f x then x else acc

... 带有两个显式参数， x和 acc .