Tema 7: Funciones de orden superior

Librerías auxiliares

import Data.Char
import Test.QuickCheck
import Test.QuickCheck.Function

1 Funciones de orden superior

Funciones de orden superior

dosVeces (*3) 2           ==  18
dosVeces reverse [2,5,7]  ==  [2,5,7]  
dosVeces :: (a -> a) -> a -> a
dosVeces f x = f (f x)
id :: a -> a
id x =  x

Usos de las funciones de orden superior

2 Procesamiento de listas

2.1 La función map

La función map: Definición

map (*2) [3,4,7]     == [6,8,14]
map sqrt [1,2,4]     == [1.0,1.4142135623731,2.0]
map even [1..5]      == [False,True,False,True,False]
map :: (a -> b) -> [a] -> [b]
map f xs =  [f x | x <- xs]
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Relación entre sum y map

sum :: [Int] -> Int
sum []     = 0                
sum (x:xs) = x + sum xs       
prop_sum_map :: [Int] -> Bool
prop_sum_map xs = sum (map (2*) xs) == 2 * sum xs
ghci> quickCheck prop_sum_map
+++ OK, passed 100 tests.

2.2 La función filter

La función filter

filter even [1,3,5,4,2,6,1] == [4,2,6]
filter (>3) [1,3,5,4,2,6,1] == [5,4,6]  
filter :: (a -> Bool) -> [a] -> [a]
filter p xs =  [x | x <- xs, p x]
filter :: (a -> Bool) -> [a] -> [a]
filter _ []                 = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

Uso conjunto de map y filter

sumaCuadradosPares [1..5]  ==  20  
sumaCuadradosPares :: [Int] -> Int
sumaCuadradosPares xs = sum (map (^2) (filter even xs))
sumaCuadradosPares' :: [Int] -> Int
sumaCuadradosPares' xs = sum [x^2 | x <- xs, even x]  

Predefinidas de orden superior para procesar listas

all odd [1,3,5]  ==  True
all odd [1,3,6]  ==  False  
any odd [1,3,5]  ==  True
any odd [2,4,6]  ==  False  
takeWhile even [2,4,6,7,8,9] == [2,4,6]  
dropWhile even [2,4,6,7,8,9] == [7,8,9]  

3 Función de plegado por la derecha: foldr

Esquema básico de recursión sobre listas

sum []         = 0
sum (x:xs)     = x + sum xs
product []     = 1
product (x:xs) = x * product xs
or []          = False
or (x:xs)      = x || or xs
and []         = True
and (x:xs)     = x && and xs

El patrón foldr

sum     = foldr (+) 0
product = foldr (*) 1
or      = foldr (||) False
and     = foldr (&&) True

Visión no recursiva de foldr

sum [2,3,5]
= foldr (+) 0 [2,3,5]       [def. de sum] 
= foldr (+) 0 2:(3:(5:[]))  [notación de lista] 
=             2+(3+(5+0))   [sustituir (:) por (+) y 
                                       []  por 0] 
= 10`                       [aritmética]
product [2,3,5]  
= foldr (*) 1 [2,3,5]      [def. de sum] 
= foldr (*) 1 2:(3:(5:[])) [notación de lista] 
=             2*(3*(5*1))  [sustituir (:) por (*) y 
                                      []  por 1] 
= 30                       [aritmética]

Definición de la longitud mediante foldr

longitud [2,3,5]
= longitud 2:(3:(5:[]))
=          1+(1+(1+0))      [Sustituciones]
= 3  
longitud :: [a] -> Int
longitud = foldr (\x y -> 1+y) 0

Definición de la inversa mediante foldr

inversa [2,3,5]
= inversa 2:(3:(5:[]))
=         (([] ++ [5]) ++ [3]) ++ [2]  [Sustituciones]
= [5,3,2]
inversa :: [a] -> [a]
inversa = foldr (\x y -> y ++ [x]) []

Definición de la concatenación mediante foldr

conc [2,3,5] [7,9]
= conc 2:(3:(5:[])) [7,9]
=      2:(3:(5:[7,9]))       [Sustituciones]
= [2,3,5,7,9]
conc xs ys = (foldr (:) ys) xs

4 Función de plegado por la izquierda: foldl

Definición de suma de lista con acumuladores

suma :: [Integer] -> Integer
suma = sumaAux 0
    where sumaAux v []     = v
          sumaAux v (x:xs) = sumaAux (v+x) xs
suma [2,3,7] 
= sumaAux 0 [2,3,7]  
= sumaAux (0+2) [3,7]  
= sumaAux 2 [3,7]  
= sumaAux (2+3) [7]  
= sumaAux 5 [7]  
= sumaAux (5+7) []  
= sumaAux 12 []
= 12  

Patrón de definición de recursión con acumulador

f v []     = v
f v (x:xs) = f (v*x) xs
suma    = foldl (+) 0
product = foldl (*) 1
or      = foldl (||) False
and     = foldl (&&) True

Definición de foldl

foldl :: (a -> b -> a) -> a -> [b ] -> a
foldl f v []     =  v
foldl f v (x:xs) =  foldl f (f v x ) xs
(foldr (-) 0) [3,4,2] =     3-(4-(2-0)) = 1
(foldl (-) 0) [3,4,2] = ((0-3)-4)-2     = -9

5 Composición de funciones

Composición de funciones

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g  = \x -> f (g x)

Uso de composición para simplificar definiciones

par n                 = not (impar n)
doVeces f x           = f (f x )
sumaCuadradosPares ns = sum (map (^2) (filter even ns))
par                = not . impar
dosVeces f         = f . f
sumaCuadradosPares = sum . map (^2) . filter even

Composición de una lista de funciones

id :: a -> a
id =  \x -> x
composicionLista [(*2),(^2)] 3       ==  18
composicionLista [(^2),(*2)] 3       ==  36
composicionLista [(/9),(^2),(*2)] 3  ==  4.0
composicionLista :: [a -> a] -> (a -> a)
composicionLista =  foldr (.) id

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

type Bit = Int

6.1 Cambio de bases

Cambio de bases: De binario a decimal

bin2int [1,0,1,1]  ==  13
bin2int [1,0,1,1]
= bin2int 1:(0:(1:(1:[])))
=         1+2*(0+2*(1+2*(1+2*0)))
= 13
bin2int :: [Bit] -> Int
bin2int =  foldr (\x y -> x + 2*y) 0

Cambio de base: De decimal a binario

int2bin 13  ==  [1,0,1,1]  
int2bin :: Int -> [Bit]
int2bin n | n < 2     = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)
int2bin 13 
= 13 `mod` 2 : int2bin (13 `div` 2)  
= 1 : int2bin (6 `div` 2)  
= 1 : (6 `mod` 2 : int2bin (6 `div` 2))
= 1 : (0 : int2bin 3)
= 1 : (0 : (3 `mod` 2 : int2bin (3 `div` 2)))
= 1 : (0 : (1 : int2bin 1))
= 1 : (0 : (1 : (1 : int2bin 0)))
= 1 : (0 : (1 : (1 : [])))
= [1,0,1,1]

Cambio de base: Comprobación de propiedades

prop_int_bin :: Int -> Bool
prop_int_bin x =
    bin2int (int2bin y) == y
    where y = abs x
ghci> quickCheck prop_int_bin
+++ OK, passed 100 tests.

6.2 Codificación y descodificación

Creación de octetos

ghci> creaOcteto [1,0,1,1,0,0,1,1,1,0,0,0]
[1,0,1,1,0,0,1,1]
ghci> creaOcteto [1,0,1,1]             
[1,0,1,1,0,0,0,0]
creaOcteto :: [Bit] -> [Bit]
creaOcteto bs =  take 8 (bs ++ repeat 0)
take 3 (repeat 5) == [5,5,5]

Codificación

ghci> codifica "abc"
[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]
codifica :: String -> [Bit]
codifica =  concat . map (creaOcteto . int2bin . ord)
concat [[1,5],[2],[4,5,3]] == [1,5,2,4,5,3]

Codificación

codifica "abc" 
= concat . map (creaOcteto . int2bin . ord) "abc"
= concat . map (creaOcteto . int2bin . ord) ['a','b','c']
= concat [creaOcteto . int2bin . ord 'a', 
          creaOcteto . int2bin . ord 'b', 
          creaOcteto . int2bin . ord 'c']
= concat [creaOcteto [1,0,0,0,0,1,1], 
          creaOcteto [0,1,0,0,0,1,1], 
          creaOcteto [1,1,0,0,0,1,1]]
= concat [[1,0,0,0,0,1,1,0], 
          [0,1,0,0,0,1,1,0], 
          [1,1,0,0,0,1,1,0]]
= [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

Separación de octetos

ghci> separaOctetos [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0]
[[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0]]
separaOctetos :: [Bit] -> [[Bit]]
separaOctetos [] = []
separaOctetos bs =  
    take 8 bs : separaOctetos (drop 8 bs)

Descodificación

ghci> descodifica [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]
"abc"
descodifica :: [Bit] -> String
descodifica =  map (chr . bin2int) . separaOctetos
descodifica [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]
= (map (chr . bin2int) . separaOctetos) 
  [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]
= map (chr . bin2int) [[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0],[1,1,0,0,0,1,1,0]]
= [(chr . bin2int) [1,0,0,0,0,1,1,0],
   (chr . bin2int) [0,1,0,0,0,1,1,0],
   (chr . bin2int) [1,1,0,0,0,1,1,0]]
= [chr 97, chr 98, chr 99]
= "abc"

Transmisión

ghci> transmite id "Texto por canal correcto"
"Texto por canal correcto"
transmite :: ([Bit] -> [Bit]) -> String -> String
transmite canal =  descodifica . canal . codifica

Corrección de la transmisión

prop_transmite :: String -> Bool
prop_transmite cs =
    transmite id cs == cs
ghci> quickCheck prop_transmite
+++ OK, passed 100 tests.

7 Bibliografía



Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla