PDF de programación - Tema 5: Definiciones de listas por comprensión - Informática (2016–17)

Tema 5: Definiciones de listas por comprensión

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 5: Definiciones de listas por comprensión

Tema 5: Definiciones de listas por comprensión

1. Generadores

2. Guardas

3. La función zip

4. Comprensión de cadenas

5. Cifrado César

Codificación y descodificación
Análisis de frecuencias
Descifrado

2 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Definiciones por comprensión

Definiciones por comprensión en Matemáticas:

{x2 : x ∈ {2, 3, 4, 5}} = {4, 9, 16, 25}

Definiciones por comprensión en Haskell:

Prelude> [x^2 | x <- [2..5]]
[4,9,16,25]

La expresión x <- [2..5] se llama un generador.
Ejemplos con más de un generador:

Prelude> [(x,y) | x <- [1,2,3], y <- [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
Prelude> [(x,y) | y <- [4,5], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

3 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Generadores dependientes

Ejemplo con generadores dependientes:

Prelude> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

(concat xss) es la concatenación de la lista de listas xss. Por

ejemplo,
concat [[1,3],[2,5,6],[4,7]] [1,3,2,5,6,4,7]

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

Prelude

4 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Generadores dependientes

Ejemplo con generadores dependientes:

Prelude> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

(concat xss) es la concatenación de la lista de listas xss. Por

ejemplo,
concat [[1,3],[2,5,6],[4,7]] [1,3,2,5,6,4,7]

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

Prelude

4 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Generadores con variables anónimas

Ejemplo de generador con variable anónima:

(primeros ps) es la lista de los primeros elementos de la lista
de pares ps. Por ejemplo,
primeros [(1,3),(2,5),(6,3)] [1,2,6]

primeros :: [(a, b)] -> [a]
primeros ps =

[x | (x,_) <- ps]

Definición de la longitud por comprensión

length :: [a] -> Int
length xs = sum [1 | _ <- xs]

Prelude

5 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Generadores con variables anónimas

Ejemplo de generador con variable anónima:

(primeros ps) es la lista de los primeros elementos de la lista
de pares ps. Por ejemplo,
primeros [(1,3),(2,5),(6,3)] [1,2,6]

primeros :: [(a, b)] -> [a]
primeros ps =

[x | (x,_) <- ps]

Definición de la longitud por comprensión

length :: [a] -> Int
length xs = sum [1 | _ <- xs]

Prelude

5 / 29

IM Tema 5: Definiciones de listas por comprensión

Generadores

Generadores con variables anónimas

Ejemplo de generador con variable anónima:

(primeros ps) es la lista de los primeros elementos de la lista
de pares ps. Por ejemplo,
primeros [(1,3),(2,5),(6,3)] [1,2,6]

primeros :: [(a, b)] -> [a]
primeros ps =

[x | (x,_) <- ps]

Definición de la longitud por comprensión

length :: [a] -> Int
length xs = sum [1 | _ <- xs]

Prelude

5 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guardas

Las listas por comprensión pueden tener guardas para restringir

los valores.

Ejemplo de guarda:

Prelude> [x | x <- [1..10], even x]
[2,4,6,8,10]
La guarda es even x.

(factores n) es la lista de los factores del número n. Por

ejemplo,
factores 30 [1,2,3,5,6,10,15,30]

factores :: Int -> [Int]
factores n = [x | x <- [1..n], n `mod` x == 0]

6 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guardas

Las listas por comprensión pueden tener guardas para restringir

los valores.

Ejemplo de guarda:

Prelude> [x | x <- [1..10], even x]
[2,4,6,8,10]
La guarda es even x.

(factores n) es la lista de los factores del número n. Por

ejemplo,
factores 30 [1,2,3,5,6,10,15,30]

factores :: Int -> [Int]
factores n = [x | x <- [1..n], n `mod` x == 0]

6 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guardas: Cálculo de primos

(primo n) se verifica si n es primo. Por ejemplo,

primo 30 False
primo 31 True

primo :: Int -> Bool
primo n = factores n == [1, n]

(primos n) es la lista de los primos menores o iguales que n.

Por ejemplo,
primos 31 [2,3,5,7,11,13,17,19,23,29,31]

primos :: Int -> [Int]
primos n = [x | x <- [2..n], primo x]

7 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guardas: Cálculo de primos

(primo n) se verifica si n es primo. Por ejemplo,

primo 30 False
primo 31 True

primo :: Int -> Bool
primo n = factores n == [1, n]

(primos n) es la lista de los primos menores o iguales que n.

Por ejemplo,
primos 31 [2,3,5,7,11,13,17,19,23,29,31]

primos :: Int -> [Int]
primos n = [x | x <- [2..n], primo x]

7 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guardas: Cálculo de primos

(primo n) se verifica si n es primo. Por ejemplo,

primo 30 False
primo 31 True

primo :: Int -> Bool
primo n = factores n == [1, n]

(primos n) es la lista de los primos menores o iguales que n.

Por ejemplo,
primos 31 [2,3,5,7,11,13,17,19,23,29,31]

primos :: Int -> [Int]
primos n = [x | x <- [2..n], primo x]

7 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guarda con igualdad

Una lista de asociación es una lista de pares formado por una

clave y un valor. Por ejemplo,
[("Juan",7),("Ana",9),("Eva",3)]

(busca c t) es la lista de los valores de la lista de asociación t

cuyas claves valen c. Por ejemplo,
Prelude> busca 'b' [('a',1),('b',3),('c',5),('b',2)]
[3,2]

busca :: Eq a => a -> [(a, b)] -> [b]
busca c t = [v | (c', v) <- t, c' == c]

8 / 29

IM Tema 5: Definiciones de listas por comprensión

Guardas

Guarda con igualdad

Una lista de asociación es una lista de pares formado por una

clave y un valor. Por ejemplo,
[("Juan",7),("Ana",9),("Eva",3)]

(busca c t) es la lista de los valores de la lista de asociación t

cuyas claves valen c. Por ejemplo,
Prelude> busca 'b' [('a',1),('b',3),('c',5),('b',2)]
[3,2]

busca :: Eq a => a -> [(a, b)] -> [b]
busca c t = [v | (c', v) <- t, c' == c]

8 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

La función zip y elementos adyacentes

(zip xs ys) es la lista obtenida emparejando los elementos de

las listas xs e ys. Por ejemplo,
Prelude> zip ['a','b','c'] [2,5,4,7]
[('a',2),('b',5),('c',4)]

(adyacentes xs) es la lista de los pares de elementos

adyacentes de la lista xs. Por ejemplo,
adyacentes [2,5,3,7] [(2,5),(5,3),(3,7)]

adyacentes :: [a] -> [(a, a)]
adyacentes xs = zip xs (tail xs)

9 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

La función zip y elementos adyacentes

(zip xs ys) es la lista obtenida emparejando los elementos de

las listas xs e ys. Por ejemplo,
Prelude> zip ['a','b','c'] [2,5,4,7]
[('a',2),('b',5),('c',4)]

(adyacentes xs) es la lista de los pares de elementos

adyacentes de la lista xs. Por ejemplo,
adyacentes [2,5,3,7] [(2,5),(5,3),(3,7)]

adyacentes :: [a] -> [(a, a)]
adyacentes xs = zip xs (tail xs)

9 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

Las funciones zip, and y listas ordenadas

(and xs) se verifica si todos los elementos de xs son

verdaderos. Por ejemplo,
True
and [2 < 3, 2+3 == 5]
and [2 < 3, 2+3 == 5, 7 < 7] False

(ordenada xs) se verifica si la lista xs está ordenada. Por

ejemplo,
ordenada [1,3,5,6,7] True
ordenada [1,3,6,5,7] False

ordenada :: Ord a => [a] -> Bool
ordenada xs = and [x <= y | (x,y) <- adyacentes xs]

10 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

Las funciones zip, and y listas ordenadas

(and xs) se verifica si todos los elementos de xs son

verdaderos. Por ejemplo,
True
and [2 < 3, 2+3 == 5]
and [2 < 3, 2+3 == 5, 7 < 7] False

(ordenada xs) se verifica si la lista xs está ordenada. Por

ejemplo,
ordenada [1,3,5,6,7] True
ordenada [1,3,6,5,7] False

ordenada :: Ord a => [a] -> Bool
ordenada xs = and [x <= y | (x,y) <- adyacentes xs]

10 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

La función zip y lista de posiciones

(posiciones x xs) es la lista de las posiciones ocupadas por el

elemento x en la lista xs. Por ejemplo,
posiciones 5 [1,5,3,5,5,7] [1,3,4]

posiciones :: Eq a => a -> [a] -> [Int]
posiciones x xs =

[i | (x',i) <- zip xs [0..n], x == x']
where n = length xs - 1

11 / 29

IM Tema 5: Definiciones de listas por comprensión

La función zip

La función zip y lista de posiciones

(posiciones x xs) es la lista de las posiciones ocupadas por el

elemento x en la lista xs. Por ejemplo,
posiciones 5 [1,5,3,5,5,7] [1,3,4]

posiciones :: Eq a => a -> [a] -> [Int]
posiciones x xs =

[i | (x',i) <- zip xs [0..n], x == x']
where n = length xs - 1

11 / 29

IM Tema 5: Definiciones de listas por comprensión

Comprensión de cadenas

Cadenas y listas

Las cadenas son listas de caracteres. Por ejemplo,

*Main> "abc" == ['a','b','c']
True

La expresión

"abc" :: String
es equivalente a
['a','b','c'] :: [Char]

Las funciones sobre listas se aplican a las cadenas:

5
length "abcde"
"edcba"
reverse "abcde"
"abcdefg"
"abcde" ++ "fg"
posiciones 'a' "Salamanca" [1,3,5,8]

12 / 29

IM Tema 5: Definiciones de listas por comprensión

Comprensión de cadenas

Definiciones sobre cadenas con comprensión

(