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.