Recursividad

• Arrancamos trabajando con definiciones recursivas sencillas, como factorial y Fibbonacci. Sobre eso pudimos ver la idea de caso recursivo y los casos de corte.
• Al crear funciones que tienen más de una definición, eso nos obliga a ver la diferencia con lógico si lo comparamos con un predicado que tenga varias cláusulas. La principal diferencia es que en lógico al trabajar con relaciones estas pueden tener más de un resultado, mientras que en funcional siempre una función va a tener un único resultado; y por lo tanto de todas las definiciones disponibles sólo evaluará una.
  ¿Cuál evalúa? La primera que matchee.
• A continuación hicimos la función par y aprovechamos para repasar compoisción al ver el caso recursivo. Tiene algunas sutilezas esa definición, la forma más fácil que encontré para que el Haskell la acepte es:
  
  par 0 = True
  par 1 = False
  par n = (not . par . subtract 1) n
  
  
  

Recursividad sobre listas

• Recordamos que al igual que en prolog, las listas son estructuras recursivas ya que se componen de una cabeza y una cola que a su vez es una lista (salvo la lista vacía, claro).
• Con eso en mente podemos intentar hacer algunas funciones simples como length, nth0 , indexOf, map y any.
• A continuación nos gustaría hacer la función filter, pero para eso debemos incorporar un concepto nuevo: guardas. Las guardas nos dan una forma alternativa al pattern matching para definir funciones en varias partes, por ejemplo:
  
  filter _ [] =[]
  filter f (x:xs) | f x       = x : filter f xs
                  | otherwise =     filter f xs
  
  
• Sabiendo eso podemos probar nosotros con la función find (ojo, sin usar filter, es para practicar recursividad).

Fold

• Finalmente definimos las funciones sumatoria, productoria y "andtoria" (hacer and de toda una lista de booleanos). Vemos que tienen una estructura muy similar:
  
  sumatoria [] = 0
  sumatoria (x:xs) = x + sumatoria xs
  
  productoria [] = 1
  productoria (x:xs) = x * productoria xs
  
  andtoria [] = True
  andtoria (x:xs) = x && andtoria xs
  
  
  
• Más concreatamente las tres tienen la misma estructura, y lo que cambia es:
• La operación que hago entre los elementos (suma, multiplicación, and)
• El valor base para la lista vacía (0, 1 o True).
  
  
• Entonces eso nos permitiría hacer una única función que reciba esas diferencias como parámetro, en Haskell esa función se llama foldr:
  
  foldr f z [] = z
  foldr f z (x:xs) = f x (foldr f z xs)
  
  
  
• Con esa definición ahora podemos redefinir las anteriores de la siguiente manera:
  
  sumatoria = foldr (+) 0
  productoria = foldr (*) 1
  andtoria = foldr (&&) True
  
  
  
• ¿Qué relación hay entre las operaciones y los valores base?
  Podemos ver que cada valor base es el valor neutro de la operación que podemos hacer.
  
  
• También se puede mencionar que el fold es más genérico que lo que hicimos hasta ahora ya que pusimos sólo ejemplos en los que el valor devuelto es del mismo tipo que los elementos de la lista, esto no tiene que ser así siempre. Pero vamos a dejar esos ejemplos para más adelante.
  
  
• Un ejemplo que sí podemos ver es el de la función mínimo. La diferencia entre esta función y las anteriores es que no es posible elegir un valor entero que sea neutro de la operación "mínimo entre dos valores". La forma más prolija de solucionar este inconveniente es tomar como valor inicial al primer elemento de la lista.
  Eso en Haskell está hecho con la función foldr1:
  
  foldr1 f (x:xs) = foldr f x xs
  
  
  Eso nos permite luego definir la función minimum así:
  
  minimum = foldr1 min
  
  
  Donde min es la función que me da el mínimo entre dos valores (ya viene con el Haskell)
  

Ejercicios para practicar

• Lo que me parece más importante a esta altura es completar toda la guía número 2, que tiene ejercicios de composición, aplicación parcial y orden superior incluyendo listas y fold.
  
• Para practicar recursividad pueden mirar la guía número 3.