PDF de programación - Tema 7: Funciones de orden superior - Informática (2016–17)

Tema 7: Funciones de orden superior

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 7: Funciones de orden superior

Tema 7: Funciones de orden superior
1. Funciones de orden superior
2. Procesamiento de listas

La función map
La función filter

3. Función de plegado por la derecha: foldr
4. Función de plegado por la izquierda: foldl
5. Composición de funciones
6. Caso de estudio: Codificación binaria y transmisión de cadenas

Cambio de bases
Codificación y descodificación

2 / 36

IM Tema 7: Funciones de orden superior

Funciones de orden superior

Funciones de orden superior

Una función es de orden superior si toma una función como

argumento o devuelve una función como resultado.

(dosVeces f x) es el resultado de aplicar f a f x. Por ejemplo,

dosVeces (*3) 2
dosVeces reverse [2,5,7] [2,5,7]

18

dosVeces :: (a -> a) -> a -> a
dosVeces f x = f (f x)

Prop: dosVeces reverse = id
donde id es la función identidad.

Prelude

id :: a -> a
id x =

x

3 / 36

IM Tema 7: Funciones de orden superior

Funciones de orden superior

Funciones de orden superior

Una función es de orden superior si toma una función como

argumento o devuelve una función como resultado.

(dosVeces f x) es el resultado de aplicar f a f x. Por ejemplo,

dosVeces (*3) 2
dosVeces reverse [2,5,7] [2,5,7]

18

dosVeces :: (a -> a) -> a -> a
dosVeces f x = f (f x)

Prop: dosVeces reverse = id
donde id es la función identidad.

Prelude

id :: a -> a
id x =

x

3 / 36

IM Tema 7: Funciones de orden superior

Funciones de orden superior

Usos de las funciones de orden superior

Definición de patrones de programación.

Aplicación de una función a todos los elementos de una lista.
Filtrado de listas por propiedades.
Patrones de recursión sobre listas.

Diseño de lenguajes de dominio específico:

Lenguajes para procesamiento de mensajes.
Analizadores sintácticos.
Procedimientos de entrada/salida.

Uso de las propiedades algebraicas de las funciones de orden

superior para razonar sobre programas.

4 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

Tema 7: Funciones de orden superior

1. Funciones de orden superior

2. Procesamiento de listas

La función map
La función filter

3. Función de plegado por la derecha: foldr

4. Función de plegado por la izquierda: foldl

5. Composición de funciones

6. Caso de estudio: Codificación binaria y transmisión de cadenas

5 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

La función map: Definición

(map f xs) es la lista obtenida aplicando f a cada elemento de

xs. Por ejemplo,
map (*2) [3,4,7]
map sqrt [1,2,4]
map even [1..5]

[6,8,14]
[1.0,1.4142135623731,2.0]
[False,True,False,True,False]

Definición de map por comprensión:

map :: (a -> b) -> [a] -> [b]
map f xs =

[f x | x <- xs]
Definición de map por recursión:

Prelude

map :: (a -> b) -> [a] -> [b]
map _ []
map f (x:xs) = f x : map f xs

= []

6 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

La función map: Definición

(map f xs) es la lista obtenida aplicando f a cada elemento de

xs. Por ejemplo,
map (*2) [3,4,7]
map sqrt [1,2,4]
map even [1..5]

[6,8,14]
[1.0,1.4142135623731,2.0]
[False,True,False,True,False]

Definición de map por comprensión:

map :: (a -> b) -> [a] -> [b]
map f xs =

[f x | x <- xs]
Definición de map por recursión:

Prelude

map :: (a -> b) -> [a] -> [b]
map _ []
map f (x:xs) = f x : map f xs

= []

6 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

La función map: Definición

(map f xs) es la lista obtenida aplicando f a cada elemento de

xs. Por ejemplo,
map (*2) [3,4,7]
map sqrt [1,2,4]
map even [1..5]

[6,8,14]
[1.0,1.4142135623731,2.0]
[False,True,False,True,False]

Definición de map por comprensión:

map :: (a -> b) -> [a] -> [b]
map f xs =

[f x | x <- xs]
Definición de map por recursión:

Prelude

map :: (a -> b) -> [a] -> [b]
map _ []
map f (x:xs) = f x : map f xs

= []

6 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

Relación entre sum y map

La función sum:

Prelude

sum :: [Int] -> Int
sum []
sum (x:xs) = x + sum xs

= 0

Propiedad: sum (map (2*) xs) = 2 * sum xs
Comprobación con QuickCheck:

prop_sum_map :: [Int] -> Bool
prop_sum_map xs = sum (map (2*) xs) == 2 * sum xs

*Main> quickCheck prop_sum_map
+++ OK, passed 100 tests.

7 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función map

Relación entre sum y map

La función sum:

Prelude

sum :: [Int] -> Int
sum []
sum (x:xs) = x + sum xs

= 0

Propiedad: sum (map (2*) xs) = 2 * sum xs
Comprobación con QuickCheck:

prop_sum_map :: [Int] -> Bool
prop_sum_map xs = sum (map (2*) xs) == 2 * sum xs

*Main> quickCheck prop_sum_map
+++ OK, passed 100 tests.

7 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

Tema 7: Funciones de orden superior

1. Funciones de orden superior

2. Procesamiento de listas

La función map
La función filter

3. Función de plegado por la derecha: foldr

4. Función de plegado por la izquierda: foldl

5. Composición de funciones

6. Caso de estudio: Codificación binaria y transmisión de cadenas

8 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

La función filter

filter p xs es la lista de los elementos de xs que cumplen la

propiedad p. Por ejemplo,
filter even [1,3,5,4,2,6,1] [4,2,6]
filter (>3) [1,3,5,4,2,6,1] [5,4,6]

Definición de filter por comprensión:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

Definición de filter por recursión:
Prelude

filter :: (a -> Bool) -> [a] -> [a]
filter _ []
filter p (x:xs) | p x

= []
= x : filter p xs

| otherwise = filter p xs

9 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

La función filter

filter p xs es la lista de los elementos de xs que cumplen la

propiedad p. Por ejemplo,
filter even [1,3,5,4,2,6,1] [4,2,6]
filter (>3) [1,3,5,4,2,6,1] [5,4,6]

Definición de filter por comprensión:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

Definición de filter por recursión:
Prelude

filter :: (a -> Bool) -> [a] -> [a]
filter _ []
filter p (x:xs) | p x

= []
= x : filter p xs

| otherwise = filter p xs

9 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

La función filter

filter p xs es la lista de los elementos de xs que cumplen la

propiedad p. Por ejemplo,
filter even [1,3,5,4,2,6,1] [4,2,6]
filter (>3) [1,3,5,4,2,6,1] [5,4,6]

Definición de filter por comprensión:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

Definición de filter por recursión:
Prelude

filter :: (a -> Bool) -> [a] -> [a]
filter _ []
filter p (x:xs) | p x

= []
= x : filter p xs

| otherwise = filter p xs

9 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

Uso conjunto de map y filter

sumaCuadradosPares xs es la suma de los cuadrados de los

números pares de la lista xs. Por ejemplo,
sumaCuadradosPares [1..5] 20

sumaCuadradosPares :: [Int] -> Int
sumaCuadradosPares xs = sum (map (^2) (filter even xs))

Definición por comprensión:

sumaCuadradosPares' :: [Int] -> Int
sumaCuadradosPares' xs = sum [x^2 | x <- xs, even x]

10 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

Uso conjunto de map y filter

sumaCuadradosPares xs es la suma de los cuadrados de los

números pares de la lista xs. Por ejemplo,
sumaCuadradosPares [1..5] 20

sumaCuadradosPares :: [Int] -> Int
sumaCuadradosPares xs = sum (map (^2) (filter even xs))

Definición por comprensión:

sumaCuadradosPares' :: [Int] -> Int
sumaCuadradosPares' xs = sum [x^2 | x <- xs, even x]

10 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

Uso conjunto de map y filter

sumaCuadradosPares xs es la suma de los cuadrados de los

números pares de la lista xs. Por ejemplo,
sumaCuadradosPares [1..5] 20

sumaCuadradosPares :: [Int] -> Int
sumaCuadradosPares xs = sum (map (^2) (filter even xs))

Definición por comprensión:

sumaCuadradosPares' :: [Int] -> Int
sumaCuadradosPares' xs = sum [x^2 | x <- xs, even x]

10 / 36

IM Tema 7: Funciones de orden superior

Procesamiento de listas

La función filter

Predefinidas de orden superior para procesar listas

all p xs se verifica si todos los elementos de xs cumplen la

any p xs se verifica si algún elemento de xs cumple la

propiedad p. Por ejemplo,
all odd [1,3,5] True
all odd [1,3,6] False

propiedad p. Por ejemplo,
any odd [1,3,5] True
any odd [2,4,6] False

takeWhile p xs es la lista de los elementos iniciales de xs que

verifican el predicado p. Por ejemplo,
takeWhile even [2,4,6,7,8,9] [2,4,6]

dropWhile p xs es la lista xs sin los elementos iniciales que

verifican el predicado p. Por ejemplo,
dropWhile even [2,4,6,7,8,9] [7,8,9]

11 / 36

IM Tema 7: Funciones de orden superior

Función de plegado por la derecha: foldr

Esquema básico de recursión sobre listas

Ejemplos de definiciones recursivas:
Prelude

= 0
= x + sum xs
= 1

sum []
sum (x:xs)
product []
product (x:xs) = x * produc