Fibonaccis y coálgebras en Haskell

Este es un archivo en modo "Haskell literario"

> x = 2
> y = (\x -> x+2) 2

"Naked expression... ", manejo de este tipo de errores.

Veamos la siguiente álgebra:
<<(+,1)>> = Naturales.
El elemento primigenio, seminal o generador es el 1, y la operación de generación
es el +.

1, 1+1=2, 1+1+1=3, 3+1, ...
1, 2, 3, ...                          
-- #N Cardinalidad de N: El tamaño del conjunto generado. La ocurrencia de un $n$
dentro de la sucesión es su orden (como conjunto ordinal).

Otro ejemplo:
<<({o, y, no},{F,T})>> = Proposiciones lógicas simples con constantes T y F.

F,T,T o F, (T o F) y (no F),...
Cfr. con Prolog.

?- false.
false.

?- true,false.
false.

?- true,true.
true.

?- \+ (true).
false.

?- false < true.
ERROR: </2: Arithmetic: `false/0' is not a function -- ya que < es definido para aritmética
?- false @< true.
true.  --ya que @< compara términos

-----------------------------------------------------------------------------

Para coálgebras:

[1],  %Primer elemento
[1,1], % segundo elemento
[1,1,1]...

en el paso al límite en el crecimiento de esta sucesión tenemos un
elemento "infinito": sería el "último" de una unión de elementos previos:

A1={[1]}
A2= A1 U {[1,1]}
A3= A2 U {[1,1,1]}
....
An = A(n-1) U {[1...replicado n veces]} (U representa la unión de conjuntos)
 A1 C A2 C A3 C A4 C A5 C ... ----> infinito (C representa la contención de conjuntos)

En el paso al límite (cuando n tiende a infinito), tenemos un conjunto infinito, cuyo
´ultimo elemento se dice que ésta en la coálgebra generada por la sucesión An.

Para el ejemplo tratado, se especifica en Haskell así:

> o = 1:o

En el modelo de computación de Haskell que es por medio de evaluación perezosa
un elemento solo se crea si se requiere en un paso de cómputo.

Así se crean los números naturales  a partir de un número n:

> nat n = n: nat(n+1)

Y así se crean todos los números naturales

> l = nat 1

Tomando l, tenemos
[1,2,3,4,5,6...] (infinitamente.

Consideremos ahora la función de Fibonacci y observemos que
si desplazamos la sucesión de Fibonacci con respecto a sí misma y
sumamos columna a columna tenemos otra vez la función de Fibonacci:
1,1,2,3,5,8...
   1,1,2,3,5,8...
____________
1 2 3 5 8 13...
Esto diría que la sucesión  de Fibonacci es más fácil de crear subcreando
dos sucesiones de Fibonacci que creando una sola! Paradójico,  no?


> fibs0 = [1,1,2,3]
> fibs1 = 1:1:[]
> fibs2 = 1:1:[x+y| x <- fibs0, y <- tail fibs0]

x valor 1 y valor 1
x valor 1 y valor 1

Tarea: Generar los números primos por medio de un flujo (comento el cofinal
de una coálgebra).


Si ahora tenemos:
fibs
obtenemos
[1,1,2,3,4,2,3,4,3,4,5,4,5,6]
que no es lo que se desea.

*Main> [x+y | x<-[1,2,3,4],y<-[5,6,7]]
[6,7,8,7,8,9,8,9,10,9,10,11]
*Main> [(x,y) | x<-[1,2,3,4],y<-[5,6,7]]
[(1,5),(1,6),(1,7),(2,5),(2,6),(2,7),(3,5),(3,6),(3,7),(4,5),(4,6),(4,7)]

Hagamos justa (fair) la selección de elementos (1 elemento por lista en cada
ocasión). Utilizamos para ello la función zip:

*Main> zip [1,2,3,4] [5,6,7]
[(1,5),(2,6),(3,7)]

*Main> [(x,y) | (x,y)<-zip [1,2,3,4] [5,6,7]]
[(1,5),(2,6),(3,7)]

*Main> [x+y | (x,y)<-zip [1,2,3,4] [5,6,7]]
[6,8,10]

Finalmente, esta es la función requerida:

> fibs = 1:1:[x+y | (x,y) <- zip fibs (tail fibs)]

He aquí algunas ejecuciones:

*Main> take 5 fibs
[1,1,2,3,5]
*Main> take 8 fibs
[1,1,2,3,5,8,13,21]
*Main> take 12 fibs
[1,1,2,3,5,8,13,21,34,55,89,144]
*Main> take 15 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]
*Main> take 20 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
*Main> fibs!!100
573147844013817084101
*Main> fibs!!200
453973694165307953197296969697410619233826

etc.

Haskell es especial

*.lhs: Hacen a Haskell intensivamente comentado.

Haskell: Su fundamento es el Cálculo Lambda (Alonzo Church, 1930s).
Haskell: Bloque de trabajo son las funciones (brazo derecho).
Haskell: Los tipos son su brazo izquierdo de trabajo: Char, Int, Float, Double...
              tipos curriados o compuestos vía productos cartesianos.
Haskell: Mónadas: La manera de Haskell de modelar el mundo exterior
               disciplinadamente.
Haskell: Funciones de mayor orden y funciones curriadas.
Haskell: Estrategia genérica de evaluación perezosa (lazy evaluation), lo que
         origina coálgebras: Las coálgebras son estructuras duales a las álgebras.
         En una álgebra queremos la intersección de inclusión; en una coálgebra
         queremos la unión de la inclusión. Las coálgebras permiten justificar la
         introducción y utilizamiento de algo conocido como objetos computacionales
         infinitos.


Ejemplos:
1) Cálculo lambda:

> (\x -> x+1) 2
> map (\x -> (4:)) [[1],[2],[3]]

>  map (\x -> x*x) [1,2,3]

> let s = sin . cos in s 2
> let f = tan . cos . sin in f 10

(Haciendo eco de las palabras del Premio Turing John Backus, de que las
variables son inútiles en la programación.)
El operador punto es composición de funciones.

2) Bloques (sin variables)

> longitud  = sum . unos
> unos = map (\x -> 1)


3) Tipos:

> lonCad :: String -> Int
> lonCad = length

Aquí se enfatiza que lonCad calcula la longitud de cadenas.

4) Visto como el programa Hello.hs.

> filter (\x -> x> 10) [1..100]

A las funciones que toman como argumento a otras funciones se les llama
funciones de mayor orden.

> productoInterno:: ((Float,Float),(Float,Float)) -> Float
> productoInterno ((x1,y1),(x2,y2)) = x1*x2+y1*y2




> productoInterno':: (Float,Float) -> (Float,Float) -> Float
> productoInterno' (x1,y1) (x2,y2) = x1*x2+y1*y2

> productoInterno'':: Float ->Float -> Float -> Float -> Float
> productoInterno''  x1 y1 x2 y2 = x1*x2+y1*y2

> mul2 :: (Float, Float) -> Float
> mul2 (x,y) = x*y+2

Versión curriada (Haskell Curry)

> mul2' :: Float -> Float -> Float
> mul2' x y = x*y+2

map (mul2 2) [1,2,3,4,5]

map (\x -> (mul2 (2,x))) [1,2,3,4,5]
La diferencia es que mul2 trabaja en el dominio (Float,Float) y
y mul2' trabaja en el dominio Funciones: Float -> Float

Esta es la versión (infame) de un programa para crear los
números de Fibonacci.
> fib 1 = 1
> fib 2 = 1
> fib n | n> 2 = fib             (n-1) + fib                 (n-2)
En una próxima ocasión generaremos su versión de flujo.


Mientras, la siguiente función genera un flujo infinito de filas del triángulo de Pascal:

> pascal = p
>   where
> p = [1] : [next a | a <- p]
> next x =  addRows (0:x) x
>                  where
>            addRows (a:x) (b:y) =  (a + b):(addRows x y)
>            addRows [a]   []    =  [a]
>            addRows []    []    =  []

Como ejemplos de ejecución tenemos:

Main> take 5 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
*Main> take 15 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1],[1,7,21,35,35,21,7,1],[1,8,28,56,70,56,28,8,1],[1,9,36,84,126,126,84,36,9,1],[1,10,45,120,210,252,210,120,45,10,1],[1,11,55,165,330,462,462,330,165,55,11,1],[1,12,66,220,495,792,924,792,495,220,66,12,1],[1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1],[1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1]]
*Main> pascal!!4
[1,4,6,4,1]
*Main> (pascal!!4)!!3
4

Los números de Fibonacci, en una infinita lista

---Lo siguiente es una pequeña perla de la programación funcional, en Haskell:

>let fibs = 1:1:[x+y|(x,y) <- zip fibs (tail fibs)] in take 17 fibs
>[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]