using lambdas as operators for "foldr"

user_470772 0
Viewed 118

So i'm following a course on Haskell, and came across defining the length function with the foldr function

so, as the length is not a primitive recursive function, we have to be more specific with the "operator" we're passing to it and, in the course, the end result is this:

len :: [a] -> Int
len = foldr (\_ n -> n + 1) 0

I think i understand the end result, but i really need clarification on the signature of the lambda function:

  • the underscore argument is supposed to be the value, which we don't care for
  • the n argument is the return of the previous call

am i right to think of it this way? or something different is happening?

haskell
1 Answers

Your assumption are correct:

  • We don't care about the elements of the list, so we can ignore them and make this clear with the underscore.
  • The n is indeed the return value of the previous call of the function. It can also be named acc standing for accumulator which makes its meaning more clear.

To be precise, as Carl pointed out, in the case of foldr, n is a thunk of nested calls of the function on elements of the list that will, if evaluated, do recursive evaluation. Thus n becomes the result of the recursive calls to foldr.

For visualization purposes:

-- how `foldr (+) 0 [1..5]` unfolds
λ> foldr (\x y -> "( " ++ x ++ " + " ++ y ++ " )") "0" $ map show [1..5]
"( 1 + ( 2 + ( 3 + ( 4 + ( 5 + 0 ) ) ) ) )"
-- how `foldl (+) 0 [1..5]` unfolds
λ> foldl (\x y -> "( " ++ x ++ " + " ++ y ++ " )") "0" $ map show [1..5]
"( ( ( ( ( 0 + 1 ) + 2 ) + 3 ) + 4 ) + 5 )"
user_77556650
Related