Geek Answers Handbook

Haskell recursive function example with foldr

I studied Haskell again after a short break, and now I'm trying to better understand how recursion and lambda expressions work in Haskell.

In this: YouTube video , there is an example of a function that calls me much more than is possible in terms of how this works:

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

For clarity, and since this was not immediately obvious to me, I will 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.

firstThat take three arguments:

  • a function that takes one argument and returns a boolean value. Since the > operator is actually an infix function, the first argument in the above example seems to be the result of a partial application to the > function - is this correct?
  • an undefined value of the same type that is expected as an absent argument to the function provided as the first argument
  • list of values ​​of the above type

But the actual firstThat function firstThat to be defined differently than its type declaration, with one argument. Since foldr usually takes the three arguments that I put together, some kind of partial application happens. The lambda expression provided as an argument to foldr also seems to have no arguments.

So how exactly does this function work? I apologize if I am too dense or do not see a forest for trees, but I just can not wrap my head around it, which is disappointing.

Any helpful explanation or example (s) is appreciated.

Thanks!

+7
lambda recursion haskell fold partial-application
source share
2 answers

But the actual firstThat function firstThat to be defined differently than its type declaration, with one argument. Since foldr usually takes the three arguments that I put together, some kind of partial application happens.

You're right. However, there is a better way to do this than talk about the “missing arguments” - one that does not make you ask where they went. Here are two ways in which arguments are missing.

First, consider this function:

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

As you know, we can also define it as follows:

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

This works because Haskell functions are values, just like any other. We can simply define the add value as equal to another (+) value, which is simply a function. There is no special syntax required to declare a function. The result is that writing arguments is explicitly (almost) never required; the main reason why we do this is because it often makes the code more readable (for example, I could define firstThat without writing the parameter f explicitly, but I won’t do it because the result is pretty disgusting).

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, creating a function of two arguments. This works for all functions of more than one argument. The key conclusion is that, at the heart of everything, all Haskell functions take only one argument. This is why a partial application works. So seeing ...

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

... you can say for sure that you explicitly specified all the parameters that firstThat accepts - that is, only one :)

The lambda expression provided as an argument to foldr does not seem to contain its arguments either.

Not really. foldr (when limited to lists) ...

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

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

 \x acc -> if fx then x else acc

... with two explicit arguments x and acc .

+5
source share

a function that takes one argument and returns a boolean value. Since the> operator is actually an infix function, the first argument in the above example seems to be the result of a partial application to the> function - is this correct?

yes: (>10) abbreviated for \x -> x > 10 , just as (10>) will be short for \x -> 10 > x .

an undefined value of the same type that is expected as an absent argument to the function provided as the first argument

First of all, this is not a missing argument: by omitting the argument, you get the value of the function. however, the type of the second argument does correspond to the argument of the function >10 , just as it corresponds to the type of the elements of the list [10,20,30,40] (which is better to argue).

list of values ​​of the above type

Yes.

But the actual firstThat function seems to be defined differently than its type declaration, with one argument. Since foldr usually takes the three arguments that I put together, some kind of partial application happens. The lambda expression provided as an argument to foldr also seems to have no arguments.

that, since the given one, for example, foo xyz = x * y * z , these two lines are equivalent:

 bar x = foo x bar xyz = foo xyz

- This is because of a concept called curry. Currying is also the reason that function type signatures are not (a, b) -> c , but instead a -> b -> c , which in turn is equivalent to a -> (b -> c) due to the correct associativity of type operator -> .

Therefore, these two lines are equivalent:

 firstThat f = foldr (\x acc -> if fx then x else acc) firstThat fxy = foldr (\x acc -> if fx then x else acc) xy

Note: you can also use Data.List.find in combination with Data.Maybe.fromMaybe :

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

See also:

+5
source share

More articles:


All Articles