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

Es sencillo, con mónadas

---------------- Y ahora lo siguiente
main :: IO ()
main = do
  putStrLn "Cuál es tu nombre?"
  name <- getLine
  putStrLn ("Gusto en conocerte, " ++ name ++ "!")

--- main tiene tipo IO (): las acciones posibles para cambiar un mundo.
--- do permite realizar acciones secuencialmente
--- Cada acción es ejecutada dentro de la mónada

--- ¿Por qué esto tendría que ser tan difícil? ¿No es este programa una nadería en la
--- programación imperativa?

--- La respuesta es: Se requiere controlar cada efecto lateral, se requiere que el programador
--- sea consciente de cada valor de una expresión, y además se requiere que haya un orden
--- para realizar consecutivamente cada acción. En resumen, se requiere control.
--- Y es que de otra forma la programación (de computadoras) permite fácilmente, sin disciplina,
--- la creación de monstruos amorfos, gelatinosos, escurridizos y fantasmagóricos: son esos
--- programas convencionales que de pronto fallan sin saber por qué, que son difíciles de dar
--- mantenimiento, de actualizar o de ampliar. Sin control, un programador entra fácilmente en
--- un terreno minado.

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]

Esta vez, Scheme

; Lo siguiente es una codificación de una interfaz ejemplificando las capacidades de
; interfaz gráficas tal como están disponibles en Racket,
; de www.racket-lang.org

mh@zas:$ cat racketNombre01.rkt
#lang racket/gui
; Creación de un diálogo

(define dialog (instantiate dialog% ("Ejemplo de diálogo")))

; Agrega un campo de texto a
(define tf (new text-field% [parent dialog] [label "Escribe tu nombre, por favor"]))

; Agrega un panel horizontal al diálogo
(define panel (new horizontal-panel% [parent dialog]
                                     [alignment '(center center)]))
; Pega un mensaje estático al diálogo
(define msg (new message% [parent dialog]
                          [label "No hay acción..."]))

; Agrega los botones de Cancel y Ok al panel horizontal
(new button% [parent panel] [label "Cancel"]
     [callback (lambda (button event)
                 (message-box "....." "NoNoNNNo  me canceles :("))])
(new button% [parent panel]
     [label "Ok"]
     [callback (lambda (button event)
                         (message-box "Respuesta"
                               (string-append "Hola  "
                                (send tf get-value)
                                )))])
(when (system-position-ok-before-cancel?)
  (send panel change-children reverse))

; Mostrar el diálogo
(send dialog show #t)

Mónadas en Haskell

---De una explicación preliminar de mónadas en Haskell
import Control.Monad
--- data Maybe t = Just t | Nothing


add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =
  case mx of
    Nothing -> Nothing
    Just x  -> case my of
                 Nothing -> Nothing
                 Just y  -> Just (x + y)

sol n =
    case n of
      2 -> 3
      4 -> 4
      5 -> 6
      _ -> 10

sol2 2 = 3
sol2 4 = 4
sol2 6 = 6
sol2 _ = 10

sol3 n | n== 2 = 3
           | n==4  = 4
           | n==5  = 6
           | otherwise = 10

add2 :: Maybe Int -> Maybe Int -> Maybe Int
add2 mx my =      
    -- Adds two values of type (Maybe Int), where each input value can be Nothing
  mx >>= (\x ->
      -- Extracts value x if mx is not Nothing
    my >>= (\y ->
     -- Extracts value y if my is not Nothing
      return (x + y)))
 -- Wraps value (x+y), returning the sum as a value of type (Maybe Int)

add3 :: Maybe Int -> Maybe Int -> Maybe Int
add3 mx my = do
  x <- mx
  y <- my
  return (x + y)

add4 :: Maybe Int -> Maybe Int -> Maybe Int
add4 = liftM2 (+)

con4 :: Maybe String -> Maybe String -> Maybe String
con4 = liftM2 (++)