Programación FuncionalHaskell
Elementos de Haskell
Programación Funcional en Haskell
Lenguajes de Programación
René Mac Kinney Romero
UAM - Iztapalapa
17 de Septiembre de 2012
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Resumen
Programación FuncionalFilosofíaModelo de reescritura
HaskellDe�nición de funcionesInterprete de HaskellListas y tiposReescritura
Elementos de HaskellEstructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
FilosofíaModelo de reescritura
Resumen
Programación Funcional
Haskell
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
FilosofíaModelo de reescritura
Resumen
Programación FuncionalFilosofíaModelo de reescritura
Haskell
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
FilosofíaModelo de reescritura
Otra forma de proponer la computación
I Basada en el Calculo Lambda de Church y Kleene
I Toda expresión computable se puede expresar como expresiónλ
I Se caracteriza por programar con valores, funciones y formasfuncionales.
I Es declarativo, se describe como son las funciones y no comocalcularlas.
I Para calcular el valor de las funciones se utiliza el modelo de lareducción β (β-redex)
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
FilosofíaModelo de reescritura
Resumen
Programación FuncionalFilosofíaModelo de reescritura
Haskell
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
FilosofíaModelo de reescritura
No importa el orden en que se evalúe una función, siempre seobtiene el mismo resultado.Es decir que podemos evaluar una expresión en cualquier orden ysiempre obtendremos el mismo resultado. Dadas
f (x) = x ∗ x + 2
g(y) = y + y
f (g(5)) = g(5) ∗ g(5) + 2 = 10 ∗ 10+ 2 = 102
= f (5+ 5) = f (10) = 10 ∗ 10+ 2 = 102
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Resumen
Programación Funcional
Haskell
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Haskell Lenguaje funcional.
Hugs Interprete que calcula formas normales.
GHC Compilador de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Resumen
Programación Funcional
HaskellDe�nición de funcionesInterprete de HaskellListas y tiposReescritura
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
La de�nición de las siguientes funciones
f x = x + 2
fact(n) = n × fact(n − 1)
fact(0) = 1
se hace en Haskell de la siguiente manera
f x = x + 2
fact (n) = n * fact (n-1)
fact (0) = 1
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
La función tiene que ir en la primera columna. Si la función ocupamás de un renglón debe tener sangría a partir del segundo renglón.
fact (n) =
n * fact (n-1)
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Resumen
Programación Funcional
HaskellDe�nición de funcionesInterprete de HaskellListas y tiposReescritura
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
prelude>_ ← cosas a evaluar
prelude> 5+5
10 ⇒ Da resultado
prelude> 23423*76342
1788158666 ⇒ Es el resultado
prelude> :? ← ayuda
prelude> \x -> x*3+sin(x)
ERROR - Cannot find "show"function for:
*** Expression : \x -> x * 3 + sin x
*** Of type : Double -> Double ⇒ Da resultado
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
prelude> (\x -> x*3+sin(x)) 4
11.2431975046921 ⇒ Es el resultado
prelude> let f = (\x -> sin(x∧2)) in f 4
-0.287903316665065 ⇒ Es el resultado
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Resumen
Programación Funcional
HaskellDe�nición de funcionesInterprete de HaskellListas y tiposReescritura
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Haskell es fuertemente tipi�cado y podemos utilizar los siguientestipos básicos:Tipo Nombre EjemploInt entero 5Fractional fracciones 3/4Float �otante 3.141592(a,b) tuplas (1,2)Char caracter 'a'[Char] cadena �Hola�
(que es una lista de caracteres 'H' 'o' 'l' 'a')Para saber el tipo de una expresión: :type [1,2] ⇒ Tipo de laexpresión
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Las listas se representan mediante la notación de corchetes.La lista
[1, 2, 3, 4, 5]
es de tipo [Int]La lista
[1, 2,′ a′,′ b′]
es inválida porque no existe un tipo que se le pueda asignar.Una lista también se puede representar utilizando el constructor : ,por ejemplo
[1, 2, 3, 4, 5] ≡ 1 : 2 : 3 : 4 : 5 : []
La lista [] es la lista vacía.
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Ejemplo
La siguiente función regresa la longitud de una lista
longitud [] = 0
longitud (x:xs) = 1 + longitud xs
Ejemplo
La siguiente función concatena dos listas
(++) [] (x:xs) = (x:xs)
(++) (y:ys) (x:xs) = y:(ys ++ (x:xs))
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Resumen
Programación Funcional
HaskellDe�nición de funcionesInterprete de HaskellListas y tiposReescritura
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Ejemplo
Con reescritura obtenemos el valor de una función
Obtener la longitud de la lista [1,2,3].longitud [1,2,3] = 1 + longitud [2,3]
= 1 + (1 + longitud [3])= 1 + (1 + (1 + longitud []))= 1 + (1 + (1 + 0)) = 3
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
longitud ([4, 5] + +[9, 8]) es:= longitud (4 : ([5] + +[9, 8]))= 1+longitud ([5] + +[9, 8]))= 1+longitud ([5] + +[9, 8])) = longitud (4 : 5 : ([] + +[9, 8]))= 1+longitud (5 : ([] + +[9, 8])) = longitud (4 : 5 : [9, 8])= 1+ 1+longitud ([] + +[9, 8])) = 1+longitud 5 : [9, 8]= 1+ 1+longitud [9, 8] = 1+ 1+longitud [9, 8]= 1+ 1+ 1+longitud [8] = 1+ 1+ 1+longitud [8]= 1+ 1+ 1+ 1+longitud [] = 1+ 1+ 1+ 1+longitud []= 1+ 1+ 1+ 1+ 0 = 1+ 1+ 1+ 1+ 0= 4 = 4
Solución 1 Solución 2
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
De�nición de funcionesInterprete de HaskellListas y tiposReescritura
Notas
Siempre se debe obtener el mismo resultado, no importando elcamino.La forma en que una expresión esta completamente reducida (esdecir ya no se puede reescribir) se llama forma normal.
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Resumen
Programación Funcional
Haskell
Elementos de Haskell
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Resumen
Programación Funcional
Haskell
Elementos de HaskellEstructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
No hay estructuras de control, pero si existe la función especial if -
then - else .
Ejemplo
Utilización de la función if-then-else en Haskell.
f x = if x > 2 then 0 else 1
g y = if y > 0 then 3
Nota: La construcción del if-then no tiene sentido, ya que siempredebe haber algo con lo cual se pueda reescribir
g (−1)
no tiene con que reescribirse.
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Resumen
Programación Funcional
Haskell
Elementos de HaskellEstructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Para comentarios se utilizan dos guiones seguidos.
-- comentario
f x = x*x -- esta función calcula el cuadrado de un número
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Resumen
Programación Funcional
Haskell
Elementos de HaskellEstructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Haskell es fuertemente tipi�cado y en la mayoría de veces elintérprete o el compilador son capaces de inferir el tipo de lafunción.
g x = x `mod` 3
El tipo inferido es1
g :: Integral a => a -> a
para expresar en Haskell un tipo se utiliza:
g :: Tipo -> Tipo
1Es decir que a es de un tipo Integral y g toma un parámetro de tipo a y
regresa un resultado de tipo a
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Resumen
Programación Funcional
Haskell
Elementos de HaskellEstructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
El prelude (preludio) de�ne la biblioteca básica de funciones, entreellas encontramos:
I head lista Regresa la cabeza de la lista.
I tail lista Regresa el resto de la lista (todos menos la cabeza).
I elemento lista Función constructor de la lista.
I zip lista1 lista2 Hace tuplas con los elementos de lista1 y lista2.
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Ejemplo
Ejemplos Preludio
prelude> head [1,2,3]
1 ⇒ cabeza de la lista.
prelude> tail [1,2,3]
[2,3] ⇒ lista sin primer elemento.
prelude> zip [] [1,2,3]
[] ⇒ lista vacia.
prelude> zip [1,2,3] [5,6,7]
[(1,5),(2,6),(3,7)] ⇒ lista de zip.
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Mas Ejemplos Preludio
Podemos de�nir:
len l = if l == [] then 0
else 1 + (len tail l)
usando el else
Ejemplo
Obtener la longitud de la lista [1, 2, 3].
1 + (len[2,3]) = 1+ (1+ len [3])=1+(1+(1+ len []))=1+(1+(1+0))=3
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Lo usual es usar la función cons (:) con la que podemos escribirlistas como x : xslen [] = 0len (x :xs)= ... mínimo un término.
Donde x es la cabeza de la lista y xs es el cuerpo.El apareamiento con el lado izquierdo de la ecuación debe ser único.⇒ len (x :xs) = 1 + len xs
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Quicksort
Ejemplo
Quicksort
quicksort [] = []
quicksort (x:xs) = (quicksort (less x xs))
++ [x] ++ (quicksort (more x xs))
less x [] = []
less x (y:ys) = if (x > y)
then y:(less x ys)
else (less x ys)
more x [] = []
more x (y:ys) = if (x < y)
then y:(more x ys)
else (more x ys)
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Mas ejemplos
Ejemplo
Función para sumar una lista de enteros.
sum [] = 0
sum (x:xs) = x + sum xs
Ejemplo
Función que suma las coordenadas x de una lista de coordenadas
sumcx [] = 0
sumcx (s:ss)= x + sumcx ss
where (x,y) = s
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Programación FuncionalHaskell
Elementos de Haskell
Estructuras de controlComentariosFuertemente tipi�cadoPreludio y Ejemplos
Ejemplo
Invierte cadena.
inv [] = []
inv (x:xs) = inv xs ++ [x]
inv [1, 2, 3] 1/x , [2, 3]/xsinv [2, 3] ++ [1]inv [3] ++ [2] ++ [1]inv [] ++ [3] ++ [2] ++ [1]⇒ [3, 2, 1]
LP 12I - René Mac Kinney Romero Programación Funcional en Haskell
Top Related