buenas, una duda teorico/practica del practico 03, estoy con el ejercicio que tenes que llevar impmentar funciones recrusivas usando solamente foldr y foldl. La duda que tengo es si foldl y foldr son intercambiables, osea entiendo que tanto con foldl o foldr puedo implemenrar funciones que hagan lo mismo, la diferencia readica en el tipo de llamada recursiva si es tail-recursive o una "recursion clasica". Lo que no me queda claro, ¿es necesario si o si en el caso de foldl agregar el acumulador de forma explicita en la funcion?
EJEMPLO: si tengo una funcion como en el practico sumSquare::[a]->a que se modela con foldr si quisiera llevarla a foldl si o si tengo que agregar a la definicion sumSquare::a->[a]->a
Practico 03 implementaciones con foldl y foldr
Número de respuestas: 1
En respuesta a Santiago Javier Alaniz Gonzalez
Re: Practico 03 implementaciones con foldl y foldr
de Marcos Viera - InCo -
Hola,
El tema es que foldr y foldl capturan esquemas de recursión distintos.
En el caso de foldr, decimos que cualquier función que tenga la forma:
h :: [a] -> b
h [ ] = e
h (x : xs) = f x (h xs)
se puede escribir como h = foldr f e.
Mientras que foldl captura definiciones de la forma:
h = h_acc e
h_acc :: b -> [a] -> b
h_acc v [ ] = v
h_acc v (x : xs) = h_acc (f v x) xs
que se pueden escribir como h = foldl f e.
Por lo que si querés pasar una función definida de forma recursiva a la aplicación de uno de los folds, la función tiene que cumplir con el esquema correspondiente.
Por ejemplo, en el caso de sumSqs, si lo pensás como una función definida en base al segundo esquema:
sumSqs_re = sumSqs_acc 0
sumSqs_acc :: Num a => a -> [a] -> a
sumSqs_acc v [] = v
sumSqs_acc v (x:xs) = sumSqs_acc (x * x + v) xs
el foldl es directo:
sumSqs_fl = foldl (\v x -> x * x + v) 0