带有foldr的Haskell递归函数示例

Question

经过短暂的中断后,我再次学习Haskell,目前我正在努力更好地理解递归和lambda表达式在Haskell中的工作原理.

在这个:YouTube视频中,就其实际工作方式而言,有一个功能示例让我感到非常困惑:

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有三个论点:

1. 一个函数,它接受一个参数并返回一个布尔值.由于>运算符实际上是一个中缀函数,上面例子中的第一个参数似乎是对>函数的部分应用的结果- 这是正确的吗？
2. 与作为第一个参数提供的函数的缺失参数相同的未指定值
3. 上述类型的值列表

但实际函数firstThat似乎与其类型声明的定义不同,只有一个参数.由于foldr通常我收集了三个参数,因此会发生某种局部应用.作为参数提供的lambda表达式foldr似乎也缺少它的参数.

那么,这个功能究竟是如何工作的呢？如果我太过茂密或者没有看到森林里的树木,我道歉,但我无法绕过它,这令人沮丧.

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

谢谢!

Answer 1

一个函数,它接受一个参数并返回一个布尔值.由于>运算符实际上是一个中缀函数,上面例子中的第一个参数似乎是>函数的部分应用的结果 - 这是正确的吗？

是的:(>10)是短的\x -> x > 10,就像(10>)是短的\x -> 10 > x.

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

首先,它不是一个缺失的论点:通过省略一个参数,你获得一个函数值.但是,第二个参数的类型确实与函数的参数匹配>10,就像它匹配列表元素的类型一样[10,20,30,40](这是更好的推理).

上述类型的值列表

是.

但实际的函数firstThat似乎与其类型声明的定义不同,只有一个参数.由于foldr通常采用我收集的三个参数,因此会发生某种部分应用.作为foldr的参数提供的lambda表达式似乎也缺少其参数.

这是因为例如foo x y z = x * y * z,这两行是等价的:

bar x     = foo x
bar x y z = foo x y z

- 这是因为一个叫做currying的概念.Currying也是函数类型签名(a, b) -> c不是a -> b -> c,而是相反,a -> (b -> c)因为->类型运算符的正确关联性.

因此,这两行是等价的:

firstThat f     = foldr (\x acc -> if f x then x else acc)
firstThat f x y = foldr (\x acc -> if f x then x else acc) x y

注意:你也可以Data.List.find结合使用Data.Maybe.fromMaybe:

?> fromMaybe 2000 $ find (>10) [10, 20, 30]
20
?> fromMaybe 2000 $ find (>10) [1, 2, 3]
2000

也可以看看:

• https://en.wikipedia.org/wiki/Currying.
• https://www.fpcomplete.com/user/EFulmer/currying-and-partial-application
• http://learnyouahaskell.com/higher-order-functions

Answer 2

但是实际函数的firstThat定义似乎与其类型声明不同，仅带有一个参数。由于foldr通常使用我收集的三个参数，因此发生了某种局部应用。

你是对的。但是，有一种比谈论“遗漏的论据”更好的方法-不会导致您询问他们去了哪里。这是不丢失参数的两种方式。

首先，请考虑以下功能：

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需要的参数-也就是，只有一个:)

作为参数提供的lambda表达式foldr似乎也缺少其参数。

并不是的。foldr（仅限于列表时）是...

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

...，因此传递给它的函数带有两个参数（鉴于上面的讨论，可以在“两个”周围添加空引号）。λ写为...

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

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