Es esta una forma correcta de escribir la Haskell foldr función?

Question

Yo estaba haciendo los ejercicios de YAHT Recursiva Tipo de datos la sección, y se encontró escrito el listFoldr función un poco difícil (sobre todo porque yo no entendía la diferencia entre foldl y foldr en un principio).Cuando finalmente me di cuenta exactamente cómo el foldr función trabajado, he decidido que un simple intercambio de argumentos de la función sería todo lo que sería necesario para cambiar mi listFoldl función a una listFoldr función:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

Esto parece que funciona (yo lo hice más pruebas de esto):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

Pero el solución dado por el ejercicio es muy diferente de la mía.Su listFoldl es exactamente la misma que la mía, pero la mirada en sus listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Qué solución es la mejor, la mía o la suya?Uno de ellos es incorrecta?(En mis pruebas, ambos terminan con el mismo resultado...)

Answer 1

Creo que se va a procesar los elementos de la 'orden inverso', por lo que el suyo no es correcta.

Usted debe ser capaz de demostrar esto con un ejemplo en el orden importa ''. Por ejemplo, algo así como

listfoldr f "" ["a", "b", "c"]

donde 'f' es una función a lo largo de las líneas de

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

donde '@' es un operador de cadena de adición (me olvido de lo que es en Haskell). El punto es sólo para 'instrumento' la función para que pueda ver qué orden se llama conseguir con los diversos argumentos.

(Tenga en cuenta que esto no se presentó en su ejemplo, porque las matemáticas "4-1-2-3" da la misma respuesta que "4-3-2-1".)

Answer 2

Su solución es definitivamente incorrecto. Ha implementado simplemente una foldl en el que la función f toma argumentos en el orden opuesto. Por ejemplo de lo que está mal, foldr (:) [] se supone que es una función de identificar en las listas, pero su función invierte la lista. Hay un montón de otras razones por las que su función no es foldr, como la forma en que funciona 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)) listas infinitas y los suyos no lo hace. Es pura coincidencia que son los mismos en su ejemplo, porque <=>. Creo que debería empezar de cero y ver cómo se supone <=> a trabajar.

Answer 3

El suyo se rompe. Prueba con algo que no termina con un único resultado numérico.

eg: listFoldr (++) "a" ["b", "c", "d"]

Usted está procesando en la dirección equivocada.

Answer 4

En una lista [x1, x2, ..., xk], su listFoldr calcula

 f xk (... (f x2 (f x1 i)) ...)

mientras que foldr debe calcular

 f x1 (f x2 (... (f xk i) ...))

(En comparación, foldl calcula

f (... (f (f i x1) x2) ...) xk

Esencialmente, listFoldr f = foldl (flip f).)

Estás de caso de prueba es desafortunado, porque

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

Cuando son las pruebas de las funciones como estas, asegúrese de pasar en un f que no es conmutativa y no asociativo (es decir, el argumento y el de aplicación de la materia), así que usted puede estar seguro de que la expresión se evalúa correctamente.Por supuesto, la resta no es conmutativa y no asociativo y simplemente tienes mala suerte.