Programación Funcional: Programando con funciones, pereza y alto orden.

 En Haskell algunos árboles binarios con nodos interiores decorados se  representan así data Bin = Hoja Int | B Int Bin Bin deriving Show La parte "Hoja Int" la podemos interpretar como las hojas del árbol, ya sin descendientes. La parte "B Int Bin Bin" hace referencia a la parte de nodos internos (raíz y no hojas) que lleva la información en la parte superior de un triángulo en "Int" y en la rama izquierda tiene un árbol de tipo Bin, así como en la parte derecha. Teniendo presente ésto, una función típica (endomorfismo) sería:   arbolConstante (Hoja n) = Hoja 2 arbolConstante (B n izq der) = B 2 (arbolConstante izq) (arbolConstante der)   Esta función toma un árbol binario y lo transforma en otro árbol binario con todo nodo valiendo 2. Otro ejemplo sería el de sumar todos los elementos de un árbol de este tipo: sumaArbol (Hoja n) = n sumaArbol (B n izq der) = n+sizq+sder               where  ...

 Scheme es un lenguaje de programación interesante, pero hay que reconocer que su sintaxis, llena de paréntesis, no parece actualizada. De todas formas, un rápido vistazo a un par de programas clásicos en este programa dará  idea de cómo programar aquí, en Scheme. (define (fact n)     (if (eq? n 0) 1         (* n (fact (- n 1))))) (define (fib n)    (if (or (eq? n 0) (eq? n 1)) 1        (+ (fib (- n 1)) (fib (- n 2))))) Como vemos, los paréntesis abundan. Podemos cargar este programa  en chez scheme, por ejemplo, y obtener: Chez Scheme Version 9.5 Copyright 1984-2017 Cisco Systems, Inc. > (load 'ejemplo.scm)   Exception in load: ejemplo.scm is not a string   Type (debug) to enter the debugger.   > (load "ejemplo.scm")   > (fact 10)   3628800   > (fib 10)   89   >  Así que los programas de fact y fib en Scheme tienen muchos p...

Para cualquier lenguaje de programación existente, la tarea de entrada y salida es algo bastante común y convencional. No tanto así para Haskell. Aquí hay varios ejemplos para, elementalmente, tratar el tema de  entrada y salida desde el punto de vista haskeliano práctico. Dado que la teoría detrás, llamada teoría de mónadas, puede parecer particularmente intimidante, la dejamos para después. Mientras, vale trabajar directamente inspirándose en los ejemplos comentados en éste capítulo:   http://learnyouahaskell.com/input-and-output

 Hemos explicado en clase algunas nociones de funciones. Ésta es la versión ingenua de la función de Fibonacci, función típica en la enseñanza de la programación por su naturaleza doblemente  recursiva. En este caso, se le deja a Haskel la discriminación por casos, por un algoritmo interno llamado "pattern matching" o casamiento de patrones. Notemos cómo cada seudo-ecuación tiene un caso que excluye a los demás.  Además, es digno notar que la parte de la barrita vertical es para ampliar las posibilidades de discriminación, con un técnica de filtrado: fib 0 = 1 fib 1 = 1 fib n | n>0 = fib(n-1)+fib(n-2) En este caso, tenemos una definición más directa que la anterior, aceptada en otros lenguajes funcionales previos, tales como Scheme (ver los sitios www.scheme.org, www.scheme.com y https://racket-lang.org/, para quienes tengan curiosidad): nfib n = if n==0 || n==1 then 1 else nfib(n-1) + nfib(n-2) Otra versión, ésta vez eficiente, y apoyada en una noción de lista infinit...

 Debido a que las funciones son componentes en la construcción de otras funciones, más complicadas, y haciendo eco de la llamada de procedimientos en lenguajes tales como C y Python, aprendemos aquí la técnica de composición de funciones.

 Repasamos aquí la teoría de conjuntos con dos propósitos: Utilizarlos como una orientación teórica en la construcción de dominios en las funciones de Haskell, y, también, utilizarlos como una estructura de datos ya provista directamente dentro de un paquete en Haskell.  Repasamos la noción de conjunto vacío, subconjunto, pertenencia, union, intersección y diferencia (complemento) de conjuntos, así como la noción de cardinalidad y de conjunto potencia.

Pensamos primero en que existen algo conocidos como "flechas". Las flechas tienen tres componentes, dos objetos, uno llamado "fuente" y otro "blanco" y un "nombre" (realmente, un morfismo). Se pueden pensar como una tripleta: (A,B,f), en donde A es la fuente, B el blanco, y f siendo el nombre). Para un conjunto de flechas, es posible que haya composición de flechas: (A,B,f) y (B,C,g) crean una nueva flecha (A,C,g o f), en donde (g o f) (composición) es el nuevo nombre de la flecha (o nuevo morfismo). a) La composición es una operación no conmutativa. b) Tiene una identidad, tal que (A,A,f) y (A,A,IdA) nos permite tener (A,A,IdA o f) = (A,A,f), por ejemplo c) La composición es una operación asociativa. d) Para algunas flechas, es posible tener flechas inversas. f) Diagramas de persecución (chasing diagrams): Son diagramas que nos permiten razonar con flechas. f A ------> B \ | \ | g g o f | \/ v ...