Librerías auxiliares
import Data.Char
import Test.QuickCheck
import Test.QuickCheck.Function
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 == 18
dosVeces reverse [2,5,7] == [2,5,7]
dosVeces :: (a -> a) -> a -> a
dosVeces f x = f (f x)
dosVeces reverse = id
, donde id
es la función identidad.id :: a -> a
id x = x
Usos de las funciones de orden superior
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] == [6,8,14]
map sqrt [1,2,4] == [1.0,1.4142135623731,2.0]
map even [1..5] == [False,True,False,True,False]
map
por comprensión:map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
map
por recursión:map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Relación entre sum
y map
sum
:sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
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
ghci> quickCheck prop_sum_map
+++ OK, passed 100 tests.
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]
filter
por comprensión:filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]
filter
por recursión: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 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))
sumaCuadradosPares' :: [Int] -> Int
sumaCuadradosPares' xs = sum [x^2 | x <- xs, even x]
Predefinidas de orden superior para procesar listas
all p xs
se verifica si todos los elementos de xs
cumplen la propiedad p
. Por ejemplo,all odd [1,3,5] == True
all odd [1,3,6] == False
any p xs
se verifica si algún elemento de xs
cumple la 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]
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
Esquema básico de recursión sobre listas:
f [] = v
f (x:xs) = x `op` (f xs)
El patrón foldr
foldr
sum = foldr (+) 0
product = foldr (*) 1
or = foldr (||) False
and = foldr (&&) True
Definición del patrón foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
Visión no recursiva de foldr
sum
: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]
sum
: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]
foldr f v xs
xs
los (:)
por f
y []
por v
.Definición de la longitud mediante foldr
longitud [2,3,5]
= longitud 2:(3:(5:[]))
= 1+(1+(1+0)) [Sustituciones]
= 3
(:)
por (\x y -> 1+y)
[]
por 0
length
usando foldr
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]
(:)
por (\x y -> y ++ [x])
[]
por []
inversa
usando foldr
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]
(:)
por (:)
[]
por ys
conc
usando foldr
conc xs ys = (foldr (:) ys) xs
foldl
Definición de suma de lista con acumuladores
suma
con acumuladores:suma :: [Integer] -> Integer
suma = sumaAux 0
where sumaAux v [] = v
sumaAux v (x:xs) = sumaAux (v+x) xs
suma
: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
sumaAux
):f v [] = v
f v (x:xs) = f (v*x) xs
foldl
:suma = foldl (+) 0
product = foldl (*) 1
or = foldl (||) False
and = foldl (&&) True
Definición de foldl
foldl
:foldl :: (a -> b -> a) -> a -> [b ] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x ) xs
foldr
y foldl
:(foldr (-) 0) [3,4,2] = 3-(4-(2-0)) = 1
(foldl (-) 0) [3,4,2] = ((0-3)-4)-2 = -9
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 fs)
es la composición de la lista de funciones fs
. Por ejemplo,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
Los números binarios se representan mediante listas de bits en orden inverso. Un bit es cero o uno. Por ejemplo, el número 1101 se representa por [1,0,1,1].
El tipo Bit
es el de los bits.
type Bit = Int
Cambio de bases: De binario a decimal
(bin2int x)
es el número decimal correspondiente al número binario x
. Por ejemplo,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 x)
es el número binario correspondiente al número decimal x
. Por ejemplo,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
int2bin
y el resultado a decimal con bin2int
se obtiene el número inicial.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.
Creación de octetos
Un octeto es un grupo de ocho bits.
(creaOcteto bs)
es el octeto correspondiente a la lista de bits bs
; es decir, los 8 primeros elementos de bs
si su longitud es mayor o igual que 8 y la lista de 8 elemento añadiendo ceros al final de bs
en caso contrario. Por ejemplo,
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)
(repeat x)
es una lista infinita cuyo único elemento es x
. Por ejemplo,take 3 (repeat 5) == [5,5,5]
Codificación
(codifica c)
es la codificación de la cadena c
como una lista de bits obtenida convirtiendo cada carácter en un número Unicode, convirtiendo cada uno de dichos números en un octeto y concatenando los octetos para obtener una lista de bits. Por ejemplo,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 xss)
es la lista obtenida concatenando la lista de listas xss
. Por ejemplo,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
(separaOctetos bs)
es la lista obtenida separando la lista de bits bs
en listas de 8 elementos. Por ejemplo,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
(descodifica bs)
es la cadena correspondiente a la lista de bits bs
. Por ejemplo,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
Los canales de transmisión pueden representarse mediante funciones que transforman cadenas de bits en cadenas de bits.
(transmite c t)
es la cadena obtenida transmitiendo la cadena t
a través del canal c
. Por ejemplo,
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.