![Page 1: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/1.jpg)
Tipos y estructuras de datos en los lenguajes funcionales
Salvador Lucas AlbaDepartamento de Sistemas Informáticos y Computación
Universidad Politécnica de Valencia
http://www.dsic.upv.es/users/elp/slucas.html
![Page 2: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/2.jpg)
ObjetivosObjetivos
• Introducir los tipos de datos como compo-nente fundamental del estilo funcional• Introducir los mecanismos de estructura-ción y abstracción de datos en los lenguajes funcionales• Presentar los tipos y estructuras de datos usuales en los lenguajes funcionales
![Page 3: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/3.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 4: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/4.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 5: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/5.jpg)
Motivación
• Evitar o detectar errores de programaciónUn tipo caracteriza el conjunto de valores que lasexpresiones de ese tipo pueden tener
• Ayudar a estructurar la informaciónLos tipos pueden verse como colecciones de valoresque comparten ciertas propiedades
• Ayudar a manejar estructuras de datosLos tipos indican cómo utilizar las estructuras de datos que comparten el mismo tipo
TiposTipos
![Page 6: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/6.jpg)
Lenguajes tipificados
• Un tipo representa el conjunto de valores que puede adoptar una variable o expresión
• En los lenguajes tipificados, las variables adoptan un tipo (ej. Pascal, Haskell)
• Los lenguajes que no restringen el rango de valores que pueden adoptar las variables son no tipificados (ej. Lisp, Prolog)
TiposTipos
![Page 7: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/7.jpg)
Lenguajes tipificadosTiposTipos
En los lenguajes funcionales modernostodas las expresiones (y subexpresiones)
tienen un tipo
![Page 8: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/8.jpg)
Lenguajes tipificados
• Los lenguajes tipificados incorporan un sistema de tipos que determina si los programas son legales
• Los sistemas de tipos se utilizan para determinar si los programas tienen un comportamiento adecuado
TiposTipos
Errores manifiestos
Errores ocultos
Limites vector
Limites vector1/01/0
![Page 9: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/9.jpg)
Lenguajes tipificados
• Un lenguaje de programación es seguro (safe) si no son posibles errores ocultos
• Los lenguajes pueden garantizar la seguridad mediante comprobaciones
estáticas (static check, ej. ML, Haskell), odinámicas (dynamic check, ej. Lisp)
TiposTipos
Compilación Ejecución
![Page 10: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/10.jpg)
Lenguajes tipificados
• En algunos lenguajes tipificados, la simple comprobación estática de tipos puede hacerlos seguros (ej. ML, Haskell)
• En otros casos, esto no es así (ej. Pascal, C)
TiposTipos
![Page 11: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/11.jpg)
Lenguajes tipificadosTiposTipos
El sistema de tipos de los lenguajes funcionales modernos garantiza la escritura
de programas seguros
![Page 12: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/12.jpg)
Lenguajes tipificados
• En los lenguajes con tipificación explícita, los tipos forman parte de la sintaxis
• En los lenguajes con tipificación implícita, los tipos no forman parte de la sintaxis
TiposTipos
Lenguajestipificados = Expresiones
de programaSistema de
tipos+
![Page 13: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/13.jpg)
Lenguajes tipificadosTiposTipos
El sistema de tipos de los lenguajes funcionales modernos permite la tipificación implícita
(debido a la posibilidad de inferencia de tipos)
![Page 14: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/14.jpg)
Expresiones de tipoSistemas de tiposSistemas de tipos
• Los tipos se describen mediante un lenguaje de expresiones de tipo:– Tipos básicos o primitivos: Bool, Char, Int, ...– Variables de tipo: a, b, c, ...– Constructores de tipo: →, ×, [ ], ...– Reglas de construcción de las expresiones:
τ ::= Bool | Char | Int | ··· | t | τ → τ | τ × τ | [ τ ] | ···
![Page 15: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/15.jpg)
Expresiones de tipoTiposTipos
Tipos monomórficos
Tipos polimórficos
Tipos básicos
Constructores de tipoVariable de tipo
• Ejemplos:• Bool, es el tipo de los valores booleanos True y
False• Int -> Int, es el tipo de la función fact, que
devuelve el factorial de un número• [ a ] -> Int, es el tipo de la función length, que
obtienen la longitud de una lista constituida por elementos de cualquier tipo
![Page 16: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/16.jpg)
AsertosSistemas de tiposSistemas de tipos
• Los sistemas de tipos permiten razonar sobre tipos y asociar expresiones de tipo con expresiones de programa:– Tipificación M :: τ (M tiene tipo τ)– Equivalencia τ = τ’ (τ y τ’ son equivalentes)– Subtipo τ<:τ’ (τ es un subtipo de τ’)
![Page 17: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/17.jpg)
SentenciasSistemas de tiposSistemas de tipos
• Las sentencias sobre las que se razona en los sistemas de tipos son de la forma:
Γ Φ
⊥Contexto de tipificación
Γ= ∅, x1::τ1, x2::τ2, ..., xn::τnpara n≥0
Aserto
Con variables libresx1, x2, ..., xn
![Page 18: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/18.jpg)
SentenciasSistemas de tiposSistemas de tipos
• Ejemplo:
∅ True::Bool⊥
∅ , x::Int x+1::Int
⊥
El tipo de True es Bool
El tipo de x+1 es Int siel tipo de x es Int
![Page 19: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/19.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Las reglas del sistema de tipos tienen la forma general:
Γ Φ⊥
Γ1 Φ1
⊥
Γn Φn⊥
... (condiciones)
(Nombre)
![Page 20: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/20.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Ejemplo:
(Env ∅ )El contexto de tipificación vacío siempre es válido
∅ ◊
⊥
![Page 21: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/21.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Ejemplo (reglas de tipificación):
Γ n::Int
⊥
(Val n)
(n=0, ±1, ±2...)Γ ◊
⊥
El tipo de un valor entero es Int en cualquier contex-to de tipificación válido
![Page 22: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/22.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Ejemplo (reglas de tipificación):
Γ M+N::Int
⊥
(Val +)
Si las expresiones M y Nson de tipo entero en Γ, también M+N lo es
Γ M::Int
⊥
Γ N::Int
⊥
![Page 23: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/23.jpg)
Lenguajes tipificadosTiposTipos
Un sistema de tipos es un conjunto dereglas de tipo
![Page 24: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/24.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Una derivación en un sistema de tipos es un árbol (invertido) de sentencias
• Cada una se obtiene de las inmediatamente superiores por aplicación de una regla
• Una sentencia válida es la que se puede obtener como raíz de una derivación
![Page 25: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/25.jpg)
Sistema formalSistemas de tiposSistemas de tipos
• Ejemplo:
∅ 1::Int
⊥
∅ 2::Int⊥
∅ 1+2::Int⊥
(por Env ∅ ) (por Env ∅ )∅ ◊
⊥
∅ ◊⊥
(por Val n) (por Val n)
(por Val +)
![Page 26: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/26.jpg)
Problemas de tipificaciónSistemas de tiposSistemas de tipos
• Dos problemas fundamentales sobre tipifica-ción de expresiones de programa:– Comprobación de tipos (type checking): Dados
M, Γ y τ, comprobar si es válida– Inferencia de tipos (type inference o type
deduction): Dada M, obtener, en su caso, Γ y τ de forma que sea válida
Γ M :: τ⊥
Γ M :: τ⊥
![Page 27: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/27.jpg)
Problemas de tipificaciónSistemas de tiposSistemas de tipos
• En ambos casos, es esencial disponer de algoritmos para realizar dichas tareas:– Algoritmo de comprobación de tipos
(typechecking algorithm)– Algoritmo de inferencia de tipos
(type inference algorithm)• La existencia y eficacia de éstos depende
mucho del sistema de tipos
![Page 28: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/28.jpg)
Problemas de tipificaciónSistemas de tiposSistemas de tipos
Haskell utiliza el sistema de tipos (polimórficos) de Hindley-Milner que admite comprobación
de tipos (Mycroft) e inferencia de tipos (Milner)
![Page 29: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/29.jpg)
Sistemas de tiposSistemas de tiposProblemas de tipificación
• El sistema de tipos de Hindley-Milner tiene sus limitaciones: la función
selfapplication f = f f
no admite ningún tipo dentro de este sistema
![Page 30: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/30.jpg)
Sistemas de tiposSistemas de tiposProblemas de tipificación
• Ejemplo: Dadas las ecuaciones
fun f lista1 lista1 = f lista1 + f lista2imposible = fun length [1,2,3] “abc”
la expresión imposible no admite ningún tipo dentro de este sistema
![Page 31: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/31.jpg)
Problemas de tipificaciónSistemas de tiposSistemas de tipos
La elección de un sistema de tipospuede limitar la expresividad del lenguaje
![Page 32: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/32.jpg)
Sistemas de tiposSistemas de tiposProblemas de tipificación
• Los algoritmos de comprobación de tipos (Mycroft) e inferencia de tipos (Milner) noson totalmente equivalentes
![Page 33: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/33.jpg)
Sistemas de tiposSistemas de tiposProblemas de tipificación
• Ejemplo: consideremos la ecuacióng x = 1:g (g ‘c’)
El algoritmo de Milner falla al tratar de encontrar el tipo de g. Especificando
g :: a -> [Int]el intérprete (que utiliza el algoritmo de Mycroft en ese caso) acepta la definición
![Page 34: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/34.jpg)
Sistemas de tiposSistemas de tiposProblemas de tipificación
• Ejemplo: consideremos la ecuacióng x = g 1
El algoritmo de Milner infiere el tipog :: Num a => a -> b
mientras que el algoritmo de Mycroft aceptala tipificación explícita (más general)
g :: a -> b
![Page 35: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/35.jpg)
Problemas de tipificaciónSistemas de tiposSistemas de tipos
A pesar de la posibilidad de tipificaciónimplícita, a veces es recomendable dar
los tipos de las funciones explícitamente
![Page 36: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/36.jpg)
Polimorfismo paramétricoPolimorfismoPolimorfismo
• Los tipos en cuya expresión de tipo no aparecen variables de tipo se denominan monotipos o tipos monomórficos
• Los tipos en cuya expresión de tipo aparecen variables se denominan politipos o tipos polimórficos (polimorfismo paramétrico)
• Un tipo polimórfico representa un número infinito de monotipos
![Page 37: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/37.jpg)
• Ejemplo: la funciónlength :: [a] -> Int
puede verse como una función con infinitos monotipos
[Int] -> Int, [Bool] -> Int, [Int -> Int] -> Int, ...
Polimorfismo paramétricoPolimorfismoPolimorfismo
![Page 38: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/38.jpg)
• Ejemplo: La implementación delength :: [a] -> Int
es única:length [ ] = 0length (x:xs) = 1+length xs
y resulta válida para todos los usos de la función
Polimorfismo paramétricoPolimorfismoPolimorfismo
![Page 39: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/39.jpg)
• Con un sistema de tipos polimórficos, el algoritmo de inferencia de tipos intenta obtener el tipo principal de las expresiones
• El tipo principal es el tipo más general capaz de capturar todos los usos válidos de la expresión
Polimorfismo paramétricoPolimorfismoPolimorfismo
![Page 40: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/40.jpg)
El sistema de tipos de Hindley-Milner asegura que toda expresión tipificable tiene
un tipo principal único
Polimorfismo paramétricoPolimorfismoPolimorfismo
![Page 41: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/41.jpg)
• A veces nos interesa sobrecargar el uso de ciertos operadores, aplicándolos sobre argumentos de distintos tipos, aunque de forma limitada
• Otras veces, no tiene sentido asignar un politipo a un operador si no podemos implementar todas sus concreciones
SobrecargaPolimorfismoPolimorfismo
![Page 42: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/42.jpg)
• Este tipo de polimorfismo se denomina polimorfismo ad-hoc o sobrecarga(overloading)
SobrecargaPolimorfismoPolimorfismo
![Page 43: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/43.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ejemplo: los operadores aritméticos (+), (-), (*), (/), ..., suelen estar sobrecargados:
(+) :: Int -> Int -> Int(+) :: Float -> Float -> Float(+) :: Complex -> Complex -> Complex
corresponden a distintos usos de (+). Otro:(+) :: Int -> Float -> Float
![Page 44: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/44.jpg)
SobrecargaPolimorfismoPolimorfismo
• El operador (+) no puede recibir el politipo(+) :: a -> a -> a
porque implicaría dotar de significado a la ‘suma’ de caracteres, funciones, listas, etc., lo cual puede interesarnos o no
![Page 45: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/45.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ejemplo: El operador de igualdad (==), aun teniendo una semántica bien definida, no es implementable en algunos casos.
¿Cómo determinar (efectivamente) si dos funciones son iguales?
![Page 46: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/46.jpg)
SobrecargaPolimorfismoPolimorfismo
• Matemáticamente: sean
f : D → E y g : D → E
dos funciones. Tenemos que
f =D → E g si y sólo si ∀ x∈ D, f(x)=E f(x)Si D es infinito, o f no es computable,
=D → E puede no ser decidible
![Page 47: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/47.jpg)
SobrecargaPolimorfismoPolimorfismo
• El operador (==) no puede recibir el politipo(==) :: a -> a -> Bool
porque tendríamos que implementar la comprobación de igualdad para todos los tipos; en particular para las funciones:
(==) :: (a->b) -> (a->b) -> Bool
![Page 48: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/48.jpg)
SobrecargaPolimorfismoPolimorfismo
En Haskell, el polimorfismo ad-hoc seimplementa mediante el concepto de clase
![Page 49: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/49.jpg)
SobrecargaPolimorfismoPolimorfismo
• Una clase es una colección de tipos• Todos los tipos pertenecientes a una clase
deben tener definidas ciertas operaciones
![Page 50: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/50.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ejemplo: – Los miembros de la clase Eq deben definir las
operaciones (==) y (/=) para comprobar si dos elementos son iguales o distintos
– Los miembros de la clase Ord deben tener definidas, además de (==) y (/=), las relaciones (<) y (<=) para comparar elementos entre sí
![Page 51: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/51.jpg)
SobrecargaPolimorfismoPolimorfismo
class Eq a where -- simplificado(==), (/=) :: a -> a -> Bool
class Eq a => Ord a where -- simplificado(<), (<=), (>), (>=) :: a -> a -> Bool
Ord es una subclase de Eq
![Page 52: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/52.jpg)
SobrecargaPolimorfismoPolimorfismo
• De acuerdo con la declaración anterior, el tipo (sobrecargado) de (==) es
(==) :: Eq a => a -> a -> Boolque se interpreta como sigue:
si a es un tipo de la clase Eq, el tipo de (==) es a -> a -> Bool
![Page 53: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/53.jpg)
SobrecargaPolimorfismoPolimorfismo
• Algunas clases predefinidas de Haskell son:– Eq: tipos con comprobación de igualdad– Ord: tipos con operadores de comparación– Enum: tipos cuyos valores son secuenciables– Show: tipos cuyos valores son convertibles en
cadenas de caracteres– Num, Integral, Fractional, Real, Floating,
RealFrac, RealFloat: clases numéricas
![Page 54: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/54.jpg)
SobrecargaPolimorfismoPolimorfismo
• Es posible añadir nuevos tipos a una clase, si particularizamos las operaciones propias de ésta para los valores del nuevo tipo
![Page 55: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/55.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ejemplo: consideremos el tipodata Nat = Cero | S Nat deriving Show
Podemos añadirlo a la clase Eq:instance Eq Nat where
Cero== Cero = TrueS n == S m = m == n_ == _ = False
![Page 56: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/56.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ejemplo: En realidad, bastaría con escribir
data Nat = Cero | S Nat deriving (Eq, Show)
![Page 57: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/57.jpg)
SobrecargaPolimorfismoPolimorfismo
• La clase Num se define como
class (Eq a, Show a) => Num a where(+),(-),(*) :: a -> a -> a
¡¡Simplificado!!
![Page 58: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/58.jpg)
SobrecargaPolimorfismoPolimorfismo
• Podemos añadir el tipo Nat a la clase Num:instance Num Nat where
Cero + n = n(S n) + m = S (n+m)Cero * n = Cero(S n) * m = m + (n*m)
No es preciso definir todas
las operaciones (¡¡pero no se podrán usar!!)
![Page 59: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/59.jpg)
SobrecargaPolimorfismoPolimorfismo
• Ahora podríamos escribir, directamente:fact Cero = S Cerofact (S n) = (S n) * fact n
¡¡Sobrecargado!!
![Page 60: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/60.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 61: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/61.jpg)
• Los tipos básicos proporcionados por Haskell son:
– Booleanos– Caracteres– Tuplas– Cadenas– Tipos numéricos
Tipos básicosTipos básicos
![Page 62: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/62.jpg)
Booleanos
• Los valores del tipo Bool son True y False
• El tipo Bool pertenece a las clases Bounded, Enum, Eq, Ord y Show, entre otras
Tipos básicosTipos básicos
![Page 63: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/63.jpg)
Booleanos
• El perfil de la clase Enum es:class Enum a where
succ,pred :: a -> atoEnum :: Int -> afromEnum :: a -> Int
Tipos básicosTipos básicos
¡¡Simplificado!!
![Page 64: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/64.jpg)
Booleanos
• Operaciones usuales para Bool (en Haskell):
– Conjunción:&& :: Bool -> Bool -> Bool– Disyunción:| | :: Bool -> Bool -> Bool– Negación: not :: Bool -> Bool
Tipos básicosTipos básicos
![Page 65: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/65.jpg)
Caracteres
• Los valores del tipo Char son los caracteres:
– ‘a’, ‘b’, ..., ‘A’, ‘B’, ..., ‘1’, ‘2’, ...– ‘\a’, ‘\b’, ‘\f’, ‘\n’, ‘\r’, ...– ‘\BEL’, ‘\BS’, ‘\FF’, ‘\LF’, ‘\CR’, ...– ‘\7’, ‘\8’, ‘\12’, ‘\10’, ‘\13’, ...– ‘\o7’, ‘\o10’, ‘\o14’, ‘\o12’, ‘\o15’– ‘\x7’, ‘\x8’, ‘\xC’, ‘\xA’, ‘\xD’, ...
Tipos básicosTipos básicos
![Page 66: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/66.jpg)
CaracteresTipos básicosTipos básicos
• El tipo Char pertenece a Bounded, Enum, Eq, Ord y Show
• Operaciones usuales para Char:– isAlpha, isAlphaNum, isAscii, isDigit,
isLower, isPrint, isUpper :: Char -> Bool– toLower, toUpper :: Char -> Char– chr :: Int -> Char -- toEnum– ord :: Char -> Int -- fromEnum
![Page 67: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/67.jpg)
Tuplas
• El tipo polimórfico (a,b) (en general, (a1,..., an) ) permite agrupar valores procedentes de tipos distintos:
(True,False) :: (Bool,Bool)(True,’a’) :: (Bool,Char)((True,False),’a’) :: ((Bool,Bool),Char)(isDigit,’a’,1) :: (Char -> Bool, Char,Int)
Tipos básicosTipos básicos
![Page 68: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/68.jpg)
Tipos básicosTipos básicos
• El tipo tupla pertenece a las clases Eq, Ord, Show y Enum, entre otras
• Operaciones usuales sobre tuplas:– Proyección izq: fst :: (a,b) -> a – Proyección der: snd :: (a,b) -> b
¡¡Sólo con pares!!
Tuplas
![Page 69: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/69.jpg)
Cadenas
• Los valores del tipo String son las cadenas de caracteres: “”, “1&bA”,“Esta frase \10ocupa dos lineas”
• En realidad, String es un tipo sinónimo:
type String = [Char]
Tipos básicosTipos básicos
![Page 70: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/70.jpg)
Tipos básicosTipos básicos
• El tipo String pertenece a las clases Eq, Ord y Show, entre otras
Cadenas
![Page 71: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/71.jpg)
Tipos numéricosTipos numéricos
• Los tipos numéricos en Haskell son:– Int, Integer: Números enteros – Float, Double: Números reales– Ratio: Números racionales– Complex: Números complejos
Números en Haskell
Preludio Estándar
Librerías
![Page 72: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/72.jpg)
Tipos numéricosTipos numéricos
• Los valores del tipo Int son los enteros de rango acotado:
0, 45, -3452, 2147493647• El límite es maxBound:: Int• El tipo Int pertenece a la clase Bounded
class Bounded a whereminBound :: amaxBound :: a
Números enteros
![Page 73: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/73.jpg)
Tipos numéricosTipos numéricos
• El tipo Int también pertenece a las clasesEnum, Eq, Ord y Show, además de a las clases numéricas Num, Real e Integral
Números enteros
![Page 74: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/74.jpg)
Tipos numéricosTipos numéricosNúmeros enteros
class (Eq a, Show a) => Num a where(+),(-),(*) :: a -> a -> anegate :: a -> aabs,signum :: a -> afromInteger :: Integer -> a
![Page 75: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/75.jpg)
Tipos numéricosTipos numéricosNúmeros enteros
class (Num a, Ord a) => Real a wheretoRational :: a -> Rational
class (Real a, Enum a) => Integral a wherequot,rem,div,mod :: a -> a -> aquotRem, divMod :: a -> a -> (a,a)toInteger :: a -> Integer
![Page 76: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/76.jpg)
Tipos numéricosTipos numéricos
• Los valores del tipo Integer son los enteros de rango arbitrario
• La aritmética con Integer es más precisa que con Int, pero más costosa
Números enteros
![Page 77: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/77.jpg)
Tipos numéricosTipos numéricos
• El tipo Integer pertenece a las clasesEnum, Eq, Ord y Show (pero no a Bounded),
además de a las clases numéricas Num, Real e Integral
Números enteros
![Page 78: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/78.jpg)
Tipos numéricosTipos numéricosNúmeros reales
• Los valores del tipo Float son los números en coma flotante de precisión simple:
0.31426, -23.12, 567.347, 4523.0231.61e7, 231.6e-2, -3.412e03
![Page 79: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/79.jpg)
Tipos numéricosTipos numéricosNúmeros reales
• El tipo Float pertenece a las clasesEnum, Eq, Ord y Show (no a Bounded),
además de a las clases numéricas Num, Real, Fractional, Floating, RealFrac y RealFloat
![Page 80: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/80.jpg)
Tipos numéricosTipos numéricosNúmeros reales
class (Num a) => Fractional a where(/) :: a -> a -> arecip :: a -> a fromRational :: Rational -> a
![Page 81: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/81.jpg)
Tipos numéricosTipos numéricosNúmeros reales
class (Fractional a) => Floating a wherepi :: aexp,log,sqrt :: a -> a (**),logBase :: a -> a -> asin,cos,tan,asin,acos,atan, sinh,cosh,tanh,asinh,acosh,atanh :: a -> a
![Page 82: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/82.jpg)
Tipos numéricosTipos numéricosNúmeros reales
class (Real a,Fractional a) => RealFrac a where
properFraction :: (Integral b) => a -> (b,a)truncate,round :: (Integral b) => a -> b ceiling,floor :: (Integral b) => a -> b
![Page 83: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/83.jpg)
Tipos numéricosTipos numéricosNúmeros reales
class (RealFrac a,Floating a) => RealFloat a where
floatRadix :: a -> IntegerfloatDigits :: a -> IntfloatRange :: a -> (Int,Int)decodeFloat :: a -> (Integer,Int)encodeFloat :: Integer -> Int -> a
![Page 84: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/84.jpg)
Tipos numéricosTipos numéricosNúmeros reales
class (RealFrac a,Floating a) => RealFloat a where -- Continuación
exponent :: a -> Intsignificand :: a -> ascaleFloat :: Int -> a -> aisNaN,isInfinite:: a -> BoolisDenormalized:: a -> BoolisIEEE :: a -> Bool
![Page 85: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/85.jpg)
Tipos numéricosTipos numéricosNúmeros reales
Otras operaciones de interés son:
(^) :: (Integral b, Num a) => a -> b -> a
(^^) :: (Integral b, Fractional a) => a -> b -> a Potencia con exponente entero
Potencia con exponente racional
![Page 86: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/86.jpg)
Tipos numéricosTipos numéricosNúmeros reales
• Los valores del tipo Double son los números en coma flotante de precisión doble
• El tipo Double pertenece a las mismas clases que Float
![Page 87: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/87.jpg)
Tipos numéricosTipos numéricosNúmeros racionales y complejos
• Los tipos Ratio y Rational, para trabajar con números racionales, se definen en la librería Ratio de Haskell 98
• El tipo Complex, para trabajar con números complejos, se definen en la librería Complex de Haskell 98
• La librería Numeric de Haskell 98describe funciones numéricas adicionales
![Page 88: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/88.jpg)
Tipos numéricosTipos numéricosNum
Int,Integer,Float,Double
RealInt,Integer,Float,Double
FractionalFloat,Double
IntegralInt,Integer
RealFracFloat,Double
RealFloatFloat,Double
FloatingFloat,Double
![Page 89: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/89.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 90: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/90.jpg)
Tipos algebraicosTiposTipos
• Los tipos algebraicos se definen junto con los valores que éstos contienen
• Ejemplos:• data Color = Red | Green | Blue• data Laboral = Lu | Ma | Mi | Ju | Vi• data TreeInt = L Int | B TreeInt TreeInt• data Tree t = L t | B (Tree t) (Tree t)
![Page 91: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/91.jpg)
Tipos algebraicosTiposTipos
• Los tipos algebraicos se definen junto con los valores que éstos contienen
• Ejemplos:• data Color = Red | Green | Blue• data Laboral = Lu | Ma | Mi | Ju | Vi• data TreeInt = L Int | B TreeInt TreeInt• data Tree t = L t | B (Tree t) (Tree t)
Constructores de tipos
![Page 92: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/92.jpg)
Tipos algebraicosTiposTipos
• Los tipos algebraicos se definen junto con los valores que éstos contienen
• Ejemplos:• data Color = Red | Green | Blue• data Laboral = Lu | Ma | Mi | Ju | Vi• data TreeInt = L Int | B TreeInt TreeInt• data Tree t = L t | B (Tree t) (Tree t)
Simples
Estructurados
Constructores de datos
![Page 93: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/93.jpg)
Tipos algebraicosTiposTipos
• Los tipos algebraicos se definen junto con los valores que éstos contienen
• Ejemplos:• data Color = Red | Green | Blue• data Laboral = Lu | Ma | Mi | Ju | Vi• data TreeInt = L Int | B TreeInt TreeInt• data Tree t = L t | B (Tree t) (Tree t)
Polimórfico Variables de tipo
![Page 94: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/94.jpg)
Tipos algebraicosTiposTipos
• Los valores se obtienen considerando la definición de tipo como una gramática:– Los constructores de datos son símbolos
terminales– Los constructores de tipo son símbolos no
terminales• Los valores del tipo son los términos del
lenguaje generado por la gramática
![Page 95: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/95.jpg)
Tipos algebraicosTiposTipos
• Ejemplo:
Int := 0 | 1 | 2 | 3 | ··· | -1 | -2 | -3 | ···TreeInt := L Int | B TreeInt TreeInt
Valores de este tipo son:
L 1, L -10, B (L 1) (L 10), B (B (L 1) (L1)) (L -1)
![Page 96: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/96.jpg)
1
4
2 3
(B (L 1) (B (B (L 2) (L 3)) (L 4)))
• Ejemplo de valor del tipo TreeInt
Tipos algebraicosTiposTipos
![Page 97: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/97.jpg)
Tipos algebraicosTiposTipos
• Las siguientes expresiones:
L (1+1) B (B (L 1) (L (length “ab”))) (L (fact 2))
son del tipo TreeInt, pero no son valores (contienen símbolos no constructores)
![Page 98: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/98.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 99: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/99.jpg)
Tipos funcionalesTipos funcionales
• Los tipos funcionales (que involucran el constructor de tipo →) son muy importantes en programación funcional
• Ejemplo: Int -> Inta -> BoolNum a => a -> a -> a(a -> b) -> [a] -> [b]
![Page 100: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/100.jpg)
Valores funcionalesTipos funcionalesTipos funcionales
• Los valores funcionales pueden especificarse de dos formas:– explícitamente: mediante expresiones lambda– implícitamente: mediante ecuaciones
![Page 101: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/101.jpg)
Expresiones lambdaDefinición de funcionesDefinición de funciones
• Una función f se describe mediante una expresión lambda de la forma
\ x1 · · · xk -> e
• Las variables x1, ..., xk son distintas entre sí y las únicas que aparecen en la expresión e
![Page 102: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/102.jpg)
Expresiones lambdaDefinición de funcionesDefinición de funciones
• Ejemplo
\ x y -> x+y\ x -> 2*x\ x -> True\ m n -> B (L m) (L n)
![Page 103: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/103.jpg)
Expresiones lambdaDefinición de funcionesDefinición de funciones
La definición de funciones recursivas esproblemática (¡aunque no imposible!)
![Page 104: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/104.jpg)
EcuacionesDefinición de funcionesDefinición de funciones
• En los lenguajes funcionales, lo normal es definir las funciones mediante ecuacionesempleando (y combinando) distintas técnicas:– parámetros formales– guardas– ajuste de patrones– distinción de casos– cláusulas where
![Page 105: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/105.jpg)
Parámetros formalesDefinición de funcionesDefinición de funciones
• Una función f se describe mediante ecuaciones de la forma:
f x1 · · · xk = r
• Las variables x1, ..., xk son distintas entre sí y las únicas que aparecen en la parte derecha r
![Page 106: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/106.jpg)
Definición de funcionesDefinición de funciones
• Ejemplos:doble x = x+xtriple x = 3*xseisveces x = doble (triple x)fact n = if n==0 then 1 else
n*fact (n-1)
Parámetros formales
![Page 107: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/107.jpg)
Definición de funcionesDefinición de funciones
• Ejemplos:doble x = x + xtriple x = 3 * x
Funciones primitivas
Parámetros formales
![Page 108: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/108.jpg)
Definición de funcionesDefinición de funciones
• Ejemplos:doble x = x+xtriple x = 3*xseisveces x = doble (triple x)
Otras funciones de usuario
Parámetros formales
![Page 109: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/109.jpg)
Definición de funcionesDefinición de funciones
• Ejemplos:doble x = x+xtriple x = 3*xseisveces x = doble (triple x)fact n = if n==0 then 1 else
n*fact (n-1)
Recursividad
Parámetros formales
![Page 110: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/110.jpg)
Parámetros formales y guardasDefinición de funcionesDefinición de funciones
• Una función f se describe mediante ecuaciones de la forma:
f x1 · · · xk | c = r
donde c es una expresión booleana
![Page 111: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/111.jpg)
Parámetros formales y guardasDefinición de funcionesDefinición de funciones
• Ejemplos:fact n | n==0 = 1
| n>0 = n*fact (n-1)sign x | x<0 = neg
| x==0 = cero| x>0 = pos
![Page 112: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/112.jpg)
Parámetros formales y guardasDefinición de funcionesDefinición de funciones
• Ejemplos:
Guardas
fact n | n==0 = 1| n>0 = n*fact (n-1)
sign x | x<0 = neg| x==0 = cero| x>0 = pos
![Page 113: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/113.jpg)
Ajuste de patronesDefinición de funcionesDefinición de funciones
• Una función f se describe mediante ecuaciones de la forma:
f p1 · · · pk = r
• Los patrones p1, ..., pk son términos constituidos por constructores de datos y variables
![Page 114: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/114.jpg)
• Ejemplos:length [] = 0length (x:xs) = 1+length xs
data Nat = Cero | S Nat
first Cero _ = []first (S n) (x:xs) = x:(first n xs)
Ajuste de patronesDefinición de funcionesDefinición de funciones
![Page 115: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/115.jpg)
• Ejemplos:
Patrones
Patrones
Ajuste de patronesDefinición de funcionesDefinición de funciones
length [] = 0length (x:xs) = 1+length xs
data Nat = Cero | S Nat
first Cero _ = []first (S n) (x:xs) = x:(first n xs)
![Page 116: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/116.jpg)
Ajuste de patronesDefinición de funcionesDefinición de funciones
• Una expresión e se ajusta a un patrón p(pattern matching) si e puede verse como una concreción de p (dando ciertos valores a las variables libres de p)
![Page 117: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/117.jpg)
Ajuste de patronesDefinición de funcionesDefinición de funciones
• Ejemplo: la expresión S (S Cero) se ajusta al patrón S x pero no al patrón Cero
S (S Cero)
S x Cero
S (S Cero)
X{x := S Cero}
![Page 118: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/118.jpg)
Ajuste de patronesDefinición de funcionesDefinición de funciones
El ajuste de patrones permite clasificar datos y explorar / recuperar subestructuras de los mismos
![Page 119: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/119.jpg)
Distinción de casosDefinición de funcionesDefinición de funciones
• Una función f se describe mediante ecuaciones de la forma:
f p1 · · · pk = case x ofq1 -> e1
...qn -> en
• Donde p1 · · · pk, q1 · · · qn son patrones, xes una variable y e1 · · · en expresiones
![Page 120: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/120.jpg)
Distinción de casosDefinición de funcionesDefinición de funciones
• Ejemplo:
length xs = case xs of[ ] -> 0(y:ys) -> 1+length ys
![Page 121: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/121.jpg)
Cláusulas whereDefinición de funcionesDefinición de funciones
• Una función f se describe mediante ecuaciones de la forma:
f p1 · · · pk = e wherel1 = r1
...ln = rn
• Donde l1 · · · ln son patrones o partes izquierdas de definiciones de función, y r1 · · · rn son expresiones
![Page 122: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/122.jpg)
Definición de funcionesDefinición de funciones
• Ejemplo:
raicesEc2 a b c = ((-b+d)/a’,(-b-d)/a’)where
d = sqrt(b^2-4*a*c)a’ = 2*a
Cláusulas where
![Page 123: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/123.jpg)
Orden superiorOrden superior
• En programación funcional, las funciones son ‘ciudadanos de primera clase’ (first class citizens):
Funciones como ciudadanos de primera clase
![Page 124: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/124.jpg)
Orden superiorOrden superior
• En programación funcional, las funciones son ‘ciudadanos de primera clase’ (first class citizens):– Pueden ser pasadas, como argumentos, a otras
funciones
Funciones como ciudadanos de primera clase
![Page 125: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/125.jpg)
• En programación funcional, las funciones son ‘ciudadanos de primera clase’ (first class citizens):– Pueden ser pasadas, como argumentos, a otras
funciones– Pueden ser devueltas como resultado de una
llamada a función
Orden superiorOrden superiorFunciones como ciudadanos de primera clase
![Page 126: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/126.jpg)
• Ejemplos:
map f [] = []map f (x:xs) = (f x):map f xs
map aplica una función fa cada elemento de una lista
add x y = x+yadd2 = add 2
add2 añade 2 al número que se le pasa como argumento
aplicaciónparcial
Orden superiorOrden superiorFunciones como ciudadanos de primera clase
![Page 127: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/127.jpg)
Currificación
• A cada función (sobre k-tuplas)f: D1 × D2 × ··· × Dk → E
le corresponde una funciónfC: D1 → (D2 → ( ··· → (Dk → E)···)
que a cada valor de D1 le asocia una función de k-1 argumentos (y viceversa)
• fC es la versión currificada de f
Orden superiorOrden superior
![Page 128: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/128.jpg)
Currificación
• Ejemplo:
map :: (a -> b) -> [a] -> [b]if :: Bool -> a -> a -> a+ :: Num a => a -> a -> a
Orden superiorOrden superior
![Page 129: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/129.jpg)
Currificación
• El operador -> es asociativo por la derecha
a -> b -> c equivale aa -> (b -> c) y difiere de (a -> b) -> c
• El operador de aplicación (a veces denotado como @) es asociativo por la izquierda
f a b equivale a (f a) b y difiere de f (a b)
Orden superiorOrden superior
![Page 130: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/130.jpg)
Currificación
• En programación funcional ésto facilita la aplicación parcial de una función: si
f :: a -> b -> cEntonces, si e::a, escribir
f etiene sentido pleno: se trata de una función
f e :: b -> c
Orden superiorOrden superior
![Page 131: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/131.jpg)
Currificación
• Ejemplo: la expresión
map add2 [1,2]
es válida en un lenguaje como Haskell, y sería equivalente a
map (add 2) [1,2] o inclusomap (+ 2) [1,2]
Orden superiorOrden superior
Sección
![Page 132: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/132.jpg)
DesarrolloDesarrollo
1. Tipos2. Tipos básicos y tipos numéricos3. Tipos algebraicos4. Tipos funcionales: orden superior,
definición de funciones5. Listas y árboles6. Tipos abstractos de datos
![Page 133: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/133.jpg)
BibliografíaBibliografía
[Car97] L. Cardelli. Type Systems.
[PE93] R. Plasmeijer and M. van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, Reading, MA, 1993
[Rea93] C. Reade. Elements of Functional Programming. Addison-Wesley, Reading, MA, 1993
![Page 134: Tipos y estructuras de datos en los lenguajes funcionales · Tipos y estructuras de datos en los lenguajes funcionales Salvador Lucas Alba Departamento de Sistemas Informáticos y](https://reader031.vdocumento.com/reader031/viewer/2022021608/5bbed8e009d3f208478cbfe2/html5/thumbnails/134.jpg)
λ :=