Lenguajes funcionales

 Esto es el producto de actividad de la semana 7: 2 programas en lenguajes funcionales distintos.


Haskell

Como agregar el resaltador de código haskell a emacs:

sudo apt-get install haskell-mode

Más información:

• haskellmode-emacs
• Haskell_mode_for_Emacs
• Random numbers

Haskell es un lenguaje hermoso, o mejor dicho "a polymorphically statically typed, lazy, purely functional language" como lo definen en la pagina oficial, es decir, un lenguaje polimorfo, fuertemente tipado, "lazy", y puramente funcional. Se le llama haskell como referencia a Haskell Brooks Curry, matemático cuyo trabajo en la lógica sentó las bases de la programación funcional.

 

Haskell B. Curry

Imágen de aquí

Foundations of mathematical logic

Imágen de aqui

Debido a su fundamento en las matemáticas y por lo tanto en conjuntos y listas, los lenguajes funcionales tienden a ser mas concisos que los imperativos y se logra hacer cosas de mayor tamaño con menor cantidad de código, por ejemplo un ordenamiento quicksort en dos líneas:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Lo anterior se lee fácilmente como: El ordenamiento de una lista vacía ([]) es una lista vacía y el ordenamiento de una lista donde el primer elemento es x y el resto es xs es la concatenación (++) de los siguientes objetos:

• Los elementos ordenados menores que x en xs.
• El elemento x.
• Los elementos ordenados mayores que x en xs.

Las cosas buenas en la mayoría de los lenguajes funcionales como haskell, lisp, erlang, scheme, ml, etc, es que al programar te concentras mas en el que quieres y no en el como lo haces, siendo una de las consecuencias una menor cantidad de errores.

Aquí están mis ejemplos de factorial de un numero y serie fibonacci respectivamente.

fac 0 = 1
fac n = n * fac (n - 1)

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Se pueden ver y entender fácilmente 3 cosas, la declaración de funciones, la llamada recursiva, y la evaluación iterativa de los parámetros que toman las funciones (de arriba a abajo).

Otra alternativa aun mas simple para el factorial (iterativo) es:

fac n = product [2..n]

Donde product es una función que toma una lista y multiplica todos sus elementos y la lista a la que nos referimos es esa que va del 2 al n. Podemos ver los tipos de variables y tipos de parámetros de funciones con el comando :t, en nuestro método recursivo se vería como:

Prelude> :t fac
fac :: (Num a) => a -> a

Que se lee como: La variable "a" es un tipo Num, la función fac toma como parámetro una variable del mismo tipo que "a" y regresa una variable del mismo tipo que "a".

Otra ventaja de haskell es que permite el cómputo en paralelo.

Pueden optar por instalar ghci ó hugs (solo intérprete):

sudo apt-get install ghc hugs

Para compilar:

ghc helloWorld.hs

Éste es mi intento de RSA. No puedo manejar bien el tipo de variable IO Integer que me devuelve Random.

import Random

rand min max = randomRIO(min, max) --regresa IO Integer


rande phi min max = if (gcd e phi == 1) && (e < phi) then e else rande phi min max
    where e = rand min max
--gcd(e, phi) == 1

randp a b | prime num = num
          | otherwise = randp a b
          where num = rand a b

prime n | list == [] = True
        | list == [n] = True
        | otherwise = False
        where list = [x | x <- 2:[3,5..round (sqrt (fromIntegral n))], n `mod` x == 0]

extGcd a b (c, d) (e, f)
    | (a > b) && r1 == 0 = (e, f)
    | (a > b) && r1 /= 0 = extGcd (a - (q1 * b)) b (c - (q1 * e), d - (q1 * f)) (e, f)
    | (a <= b) && r2 == 0 = (c, d)
    | (a <= b) && r2 /= 0 = extGcd a (b - (q2 * a)) (c, d) (e - (q2 * c), f - (q2 * d))
    where
      r1 = a `mod` b
      r2 = b `mod` a
      q1 = a `div` b
      q2 = b `div` a
             
egcd a b = extGcd a b (1, 0) (0, 1)

getPvte x y = fst (egcd x y)

cifrar m e n = (m ^ e) `mod` n
decifrar c d n = (c ^ d) `mod` n

primos = do let min = 2
                max = 10000
            p <- randp min max
            q <- randp min max
            let 
                n = (p * q)
                phi = (p - 1) * (q - 1)
            e <- rande phi min max
            d <- getPvte e phi
            let
                mensaje = 27436
            c <- cifrar mensaje e n
            print c
            d <- decifrar c d n
            print d
   

Tutoriales RSA:

• The Euclidean Algorithm and the Extended Euclidean Algorithm 
• An interactive Extended Euclidean Algorithm

Aprender haskell, lo mas recomendable es que lean el inicio rápido de la página oficial. Seguido de los tutoriales:

•  A gentle introduction to haskell
• Haskell tutorial for C programmers
• Learn you a haskell
• Haskell reference

Scheme

Lenguaje funcional impuro y un dialecto principal de lisp, desarrollado en el laboratorio de IA del MIT por Guy L. Steele y Gerald Jay Sussman.

Su simple sintáxis se basa en las expresiones S, una listas encerradas en paréntesis donde el operador va seguido de sus argumentos. Scheme es poderoso para manejar listas debido a su herencia por parte de Lisp con primitivas como cons, car y cdr.

Aquí esta mi ejemplo de quicksort que se parece al de haskell (concatena listas filtradas).

(define (qsort lista)
  (if (> (length lista) 1)
      (append
       (qsort (filter (lambda (x) (< x (car lista))) (cdr lista)))
       (cons (car lista) '())
       (qsort (filter (lambda (x) (> x (car lista))) (cdr lista)))
       ) lista 
  )
)