tipos y estructuras de datos en los lenguajes funcionales · tipos y estructuras de datos en los...

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

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

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

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

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

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

Lenguajes tipificadosTiposTipos

En los lenguajes funcionales modernostodas las expresiones (y subexpresiones)

tienen un tipo

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

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

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

Lenguajes tipificadosTiposTipos

El sistema de tipos de los lenguajes funcionales modernos garantiza la escritura

de programas seguros

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+

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)

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 | τ → τ | τ × τ | [ τ ] | ···

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

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 τ’)

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

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

Sistema formalSistemas de tiposSistemas de tipos

• Las reglas del sistema de tipos tienen la forma general:

Γ Φ⊥

Γ1 Φ1

⊥

Γn Φn⊥

... (condiciones)

(Nombre)

Sistema formalSistemas de tiposSistemas de tipos

• Ejemplo:

(Env ∅ )El contexto de tipificación vacío siempre es válido

∅ ◊

⊥

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

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

⊥

Lenguajes tipificadosTiposTipos

Un sistema de tipos es un conjunto dereglas de tipo

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

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 +)

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 :: τ⊥

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

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)

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

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

Problemas de tipificaciónSistemas de tiposSistemas de tipos

La elección de un sistema de tipospuede limitar la expresividad del lenguaje

Sistemas de tiposSistemas de tiposProblemas de tipificación

• Los algoritmos de comprobación de tipos (Mycroft) e inferencia de tipos (Milner) noson totalmente equivalentes

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

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

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

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

• 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

• 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

• 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

El sistema de tipos de Hindley-Milner asegura que toda expresión tipificable tiene

un tipo principal único

Polimorfismo paramétricoPolimorfismoPolimorfismo

• 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

• Este tipo de polimorfismo se denomina polimorfismo ad-hoc o sobrecarga(overloading)

SobrecargaPolimorfismoPolimorfismo

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

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

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?

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

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

SobrecargaPolimorfismoPolimorfismo

En Haskell, el polimorfismo ad-hoc seimplementa mediante el concepto de clase

SobrecargaPolimorfismoPolimorfismo

• Una clase es una colección de tipos• Todos los tipos pertenecientes a una clase

deben tener definidas ciertas operaciones

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í

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

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

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

SobrecargaPolimorfismoPolimorfismo

• Es posible añadir nuevos tipos a una clase, si particularizamos las operaciones propias de ésta para los valores del nuevo tipo

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

SobrecargaPolimorfismoPolimorfismo

• Ejemplo: En realidad, bastaría con escribir

data Nat = Cero | S Nat deriving (Eq, Show)

SobrecargaPolimorfismoPolimorfismo

• La clase Num se define como

class (Eq a, Show a) => Num a where(+),(-),(*) :: a -> a -> a

¡¡Simplificado!!

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!!)

SobrecargaPolimorfismoPolimorfismo

• Ahora podríamos escribir, directamente:fact Cero = S Cerofact (S n) = (S n) * fact n

¡¡Sobrecargado!!

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

• Los tipos básicos proporcionados por Haskell son:

– Booleanos– Caracteres– Tuplas– Cadenas– Tipos numéricos

Tipos básicosTipos básicos

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

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!!

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

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

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

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

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

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

Tipos básicosTipos básicos

• El tipo String pertenece a las clases Eq, Ord y Show, entre otras

Cadenas

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

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

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

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

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

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

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

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

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

Tipos numéricosTipos numéricosNúmeros reales

class (Num a) => Fractional a where(/) :: a -> a -> arecip :: a -> a fromRational :: Rational -> a

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

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

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

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

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

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

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

Tipos numéricosTipos numéricosNum

Int,Integer,Float,Double

RealInt,Integer,Float,Double

FractionalFloat,Double

IntegralInt,Integer

RealFracFloat,Double

RealFloatFloat,Double

FloatingFloat,Double

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

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)

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

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

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

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

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)

1

4

2 3

(B (L 1) (B (B (L 2) (L 3)) (L 4)))

• Ejemplo de valor del tipo TreeInt

Tipos algebraicosTiposTipos

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)

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

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]

Valores funcionalesTipos funcionalesTipos funcionales

• Los valores funcionales pueden especificarse de dos formas:– explícitamente: mediante expresiones lambda– implícitamente: mediante ecuaciones

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

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)

Expresiones lambdaDefinición de funcionesDefinición de funciones

La definición de funciones recursivas esproblemática (¡aunque no imposible!)

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

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

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

Definición de funcionesDefinición de funciones

• Ejemplos:doble x = x + xtriple x = 3 * x

Funciones primitivas

Parámetros formales

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

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

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

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

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

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

• 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

• 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)

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)

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}

Ajuste de patronesDefinición de funcionesDefinición de funciones

El ajuste de patrones permite clasificar datos y explorar / recuperar subestructuras de los mismos

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

Distinción de casosDefinición de funcionesDefinición de funciones

• Ejemplo:

length xs = case xs of[ ] -> 0(y:ys) -> 1+length ys

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

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

Orden superiorOrden superior

• En programación funcional, las funciones son ‘ciudadanos de primera clase’ (first class citizens):

Funciones como ciudadanos de primera clase

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

• 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

• 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

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

Currificación

• Ejemplo:

map :: (a -> b) -> [a] -> [b]if :: Bool -> a -> a -> a+ :: Num a => a -> a -> a

Orden superiorOrden superior

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

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

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

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

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

λ :=