Determine length with foldr

Question

I am trying to understand some of the lectures in the class that I accept. It defines a length function as:

length = foldr (\_ n -> 1 + n) 0 

Can someone explain to me how this works? I can not think it over.

Answer 1

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

Taking use in context, foldr takes three arguments: a function (which takes element a and a list of elements and b) the accumulator and returns the accumulator), the initial value of the accumulator, and the list. foldr returns the final battery result after applying the function through a list.

Regarding this piece of code:

 length = foldr (\_ n -> 1 + n) 0 

As you can see, there is no list in it - therefore, the return value of the right side is a function that will take in the list and create an Int (the same type as 0 ). Type: [a] -> Int .

Regarding the right side: (\_ n -> 1 + n) 0

\ means declaring an unnamed function

_ means to ignore the element from the list (corresponds to a in type foldr ). As you know, foldr will go to the list and apply a function to each element. This is the element passed to the function. We do not use it in the length function, therefore, we will indicate that it should be ignored.

n is a parameter for Int passed as battery.

-> means return

1 + n will increase the battery. You can imagine that the return value is passed back to foldr and foldr saves the value to go to the next function call (\_ n -> 1 + n) .

0 outside the bracket is the initial value of the counter.

Answer 2

The foldr function is to collapse the list using the correct associative operator, you can easily understand what this function does if you use the (+) operator (the function has the same behavior as sum ):

 foldr (+) 0 [1,2,3,4,5] = 1+(2+(3+(4+(5+0)))) 

For your length function, it is equivalent to:

 foldr (\_ n -> 1 + n) 0 [1,2,3,4,5] = 1+(1+(1+(1+(1+0)))) 

Here is what foldr for

Answer 3

There are several equivalent ways to figure this out. First: foldr fz [1, 2, 3, 4, ..., n] calculates the following value:

 f 1 (f 2 (f 3 (f 4 (f ... (fnz))))) 

So in your case:

 length [1,2,3,4] = foldr (\_ n -> 1 + n) 0 [1,2,3,4] = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 ((\_ n -> 1 + n) 4 0))) = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 (1 + 0))) = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 (1 + (1 + 0))) = (\_ n -> 1 + n) 1 (1 + (1 + (1 + 0))) = 1 + (1 + (1 + (1 + 0))) = 1 + (1 + (1 + 1)) = 1 + (1 + 2) = 1 + 3 = 4 

Another task is to start with this function, which copies the list:

 listCopy :: [a] -> [a] listCopy [] = [] listCopy (x:xs) = x : listCopy xs 

It may look like a trivial function, but foldr is basically such that, in addition to hard coding an empty list [] and a pair constructor : on the right side, instead we use some arbitrary constant and a function provided as arguments. I sometimes like to call these arguments fakeCons and fakeNil ( cons and nil are the names of the operator : and constants [] in Lisp), because in a sense, re "copy" the list, but using fake constructors:

 foldr fakeCons fakeNil [] = fakeNil foldr fakeCons fakeNil (x:xs) = fakeCons x (subfold xs) where subfold = foldr fakeCons fakeNil 

So, with this interpretation, your length function “copies” the list, except that instead of using an empty list, it uses 0 , and instead : it discards the elements and adds 1 to the total.

And here's the third foldr fz xs intuition:

• z is the solution to your problem when the list is empty.
• f is a function that takes two arguments: a list item and a partial solution : a solution to your problem for a list of items that appear to the right of the item that went to f . f then creates a solution that is "one element more."

So in the case of length :

• The length of the empty list is 0, so why are you using 0 as the second argument to foldr .
• If the length xs is n , then the length x:xs is n+1 . This is what your first argument to foldr , \_ n -> n + 1 does: it computes the length of the list given as arguments by the first element of the list (which we ignore in this case) and the length of the rest of the list ( n ).

This foldr way of thinking is very powerful and should not be underestimated. Basically, in the function that you pass as the first argument to foldr , you can assume that the problem you are trying to solve is already solved for all lists shorter than the one you are dealing with. Thus, your entire argument function should calculate the answer for a list that is one item longer.