Definiton de longitud usando foldr

Question

Estoy tratando de entender una parte en las notas de clase de una clase que estoy tomando. Define la función de longitud como:

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

¿Alguien me puede explicar cómo funciona esto? No puedo entenderlo.

Answer 1

En primer lugar, el tipo de foldr: (a -> b -> b) -> b -> [a] -> b

Tomando el uso en contexto, foldr toma en 3 argumentos: una función (que toma en un un elemento de una lista y b un acumulador,.. y devuelve el acumulador), el valor inicial del acumulador y una lista. foldr devuelve el resultado final del acumulador después de aplicar la función a través de la lista.

En cuanto a este pedazo de código:

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

Como se puede ver, no se encuentra la lista - por lo que el valor de retorno de la derecha es una función que le llevará en una lista y producir una Int (el mismo tipo que 0). Tipo: [a] -> Int.

cuanto a lo que significa el lado derecho: (\_ n -> 1 + n) 0

\ medios declaran una función sin nombre

_ medios ignoran el elemento de la lista (corresponden a a en el tipo de foldr). Como sabe, foldr revisará la lista y aplicará la función a cada elemento. Este es el elemento pasado a la función. No tenemos ningún uso en una función length, por lo que denotamos que debe ignorarse.

n es el parámetro para el Int pasado como acumulador.

-> medios de retorno

1 + n incrementará el acumulador. Puede imaginar que el valor devuelto se devuelve a foldr y foldr guarda el valor para pasar a la siguiente llamada a la función (\_ n -> 1 + n).

El 0 fuera del soporte es el valor de inicio del contador.

Answer 2

La función foldr es doblar la lista con un operador asociativo adecuado, se puede entender fácilmente lo que hace la función de si se utiliza el operador (+), (La función tiene el mismo comportamiento que sum):

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

para su función de longitud, que es equivalente a:

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

Eso es lo que el foldr para

Answer 3

Hay varias formas equivalentes de entenderlo.Primero: foldr f z [1, 2, 3, 4, ..., n] calcula el siguiente valor:

f 1 (f 2 (f 3 (f 4 (f ... (f n z))))) 

Así, en su caso:

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 

Otra es que partir de esta función, que copia una lista:

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

Eso puede parecer una función trivial, pero foldr es básicamente eso, pero excepto el código duro de la lista vacía [] y el constructor de pares : en el lado derecho, en su lugar usamos algunas constantes y funciones arbitrarias proporcionadas como argumentos. A veces me gusta llamar a estos argumentos fakeCons y fakeNil (cons y nil son los nombres de operador : y [] constante en el lenguaje Lisp), porque en un sentido que está "copia" la lista, pero el uso de constructores falsos:

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

Así, bajo esta interpretación, su función es length "copia" de una lista, excepto que en lugar de la lista vacía se trata de utilizar 0, y en vez de : es descartando los elementos y sumando 1 al total acumulado.

Y aquí es todavía una tercera INTERPRETACIÓN de foldr f z xs:

1. z es la solución de su problema cuando la lista está vacía.
2. f es una función que toma dos argumentos: un elemento de la lista, y una solución parcial: la solución a su problema de la lista de elementos que aparecen a la derecha del elemento que se pasa a f. f produce una solución que es "un elemento más grande".

Así, en el caso de length:

1. La longitud de una lista vacía es 0, así que por eso se utiliza 0 como segundo argumento a foldr.
2. Si la longitud de xs es n, entonces la longitud de x:xs es n+1. Eso es lo que está haciendo su primer argumento al foldr, \_ n -> n + 1: está calculando la longitud de una lista, dado como argumentos el primer elemento de la lista (que en este caso ignoramos) y la longitud del resto de la lista (n) .

Esta manera de pensar acerca de foldr es muy poderosa, y no debe subestimarse. Básicamente, en la función que pasa como el primer argumento en foldr, puede suponer que el problema que está tratando de resolver ya se ha resuelto para todas las listas más cortas que la que está tratando. Toda su función de argumento tiene que hacer, entonces, es calcular una respuesta para una lista que es un elemento más larga.