Haskell用foldr递归函数示例 [英] Haskell recursive function example with foldr

问题描述

>在此： YouTube视频中，有一个函数示例让我对它的实际工作方式感到疑惑不止：

  firstThat ::（a  - > Bool） - > a  - > [a]  - > a 
 firstThat f = foldr（\ x acc  - > if fx then x else acc）
  

为了清楚起见，既然它对我来说不是很明显，我将举一个例子来将这个函数应用于一些参数：

pre > firstThat（> 10）2000 [10,20,30,40] --returns 20，但如果列表中没有值大于10


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

似乎 firstThat 有三个参数：

1. 一个函数接受一个参数并返回一个布尔值。由于> 运算符实际上是一个中缀函数，因此上例中的第一个参数似乎是对> 函数 - 是否正确？


2. 预期为作为第一个参数提供的函数缺少参数的相同类型的未指定值


3. 上述类型的值列表

但实际的函数 firstThat 似乎被定义为与其类型声明不同，只有一个参数。由于 foldr 通常需要我收集的三个参数，因此会出现某种部分应用程序。作为 foldr 参数提供的lambda表达式似乎也缺少它的参数。

所以，这个功能有效吗？我很抱歉，如果我太密集或无法看到树木的森林，但我不能包围我的头，这是令人沮丧的。

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

谢谢！ 解决方案

blockquote>

但实际函数 firstThat 似乎与其类型声明的定义不同，只有一个参数。由于 foldr 通常需要三个参数，我收集到的是某种部分应用程序发生。

你说得对。然而，有一个更好的方式来说明它，而不是谈论缺少的论点 - 一个不会让你去问问他们去哪里的问题。首先，考虑这个函数：

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

您可能知道，我们也可以定义它像这样：

  add :: Num a => a  - > a  - > a 
 add =（+）
  

这是可行的，因为Haskell函数的值是任何其他值。我们可以简单地将一个值 add 定义为等于另一个值（+），这恰好发生在是一个功能。声明函数不需要特殊的语法。结果是明确地写出论点是（几乎）不需要的;我们这样做的主要原因是因为它经常使代码更具可读性（例如，我可以定义 firstThat 而无需编写 f / p>



  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 fx then x else acc）
  

...你可以准确地说你已经明确地写过 firstThat 所需的所有参数 - 也就是说只有一个：）

---

作为参数提供给 foldr 的lambda表达式似乎是也缺少它的论据。

并非如此。 foldr （限于列表时）是...

  foldr： ：（a  - > b  - > b） - > b  - > [a]  - > b 
  

...传递给它的函数有两个参数（随意添加空引号围绕两个，给出上面的讨论）。拉姆达被写为...

  \x acc  - >如果fx then x else acc 
  

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

I've taken up learning Haskell again, after a short hiatus and I am currently trying to get a better understanding of how recursion and lambda expressions work in Haskell.

In this: YouTube video, there is a function example that puzzles me far more than it probably should, in terms of how it actually works:

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

For the sake of clarity and since it wasn't immediately obvious to me, I'll give an example of applying this function to some arguments:

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

Please correct me, if my assumptions are wrong.

It seems firstThat takes three arguments:

1. a function that takes one arguments and returns a Boolean value. Since the > operator is actually an infix function, the first argument in the example above seems the result of a partial application to the > function – is this correct?
2. an unspecified value of the same type expected as the missing argument to the function provided as the first argument
3. a list of values of the aforementioned type

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. The lambda expression provided as an argument to foldr seem to be missing its arguments too.

So, how exactly does this function work? I apologize if I am being too dense or fail to see the forest for the trees, but I just cannot wrap my head around it, which is frustrating.

Any helpful explanation or example(s) would be greatly appreciated.

Thanks!

解决方案

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.

You are right. However, there is a nicer way of putting it than talking about "missing arguments" -- one that doesn't lead you into asking where they have gone. Here are two ways in which the arguments are not missing.

Firstly, consider this function:

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

As you may know, we can also define it like this:

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

That works because Haskell functions are values like any other. We can simply define a value, add, as being equal to another value, (+), which just happens to be a function. There is no special syntax required to declare a function. The upshot is that writing arguments explicitly is (almost) never necessary; the main reason why we do so because it often makes code more readable (for instance, I could define firstThat without writing the f parameter explicitly, but I won't do so because the result is rather hideous).

Secondly, whenever you see a function type with three arguments...

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

... you can also read it like this...

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

... that is, a function of one argument that produces a function of two arguments. That works for all functions of more than one argument. The key takeaway is that, at heart, all Haskell functions take just one argument. That is why partial application works. So on seeing...

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

... you can accurately say that you have written explicitly all parameters that firstThat takes -- that is, only one :)

---

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

Not really. foldr (when restricted to lists) is...

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

... and so the function passed to it takes two arguments (feel free to add air quotes around "two", given the discussion above). The lambda was written as...

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

... with two explicit arguments, x and acc.

这篇关于Haskell用foldr递归函数示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！