Tema 11: Aplicaciones de programación funcional
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 11: Aplicaciones de programación funcional
Tema 11: Aplicaciones de programación funcional
1. El juego de cifras y letras
Introducción
Búsqueda de la solución por fuerza bruta
Búsqueda combinando generación y evaluación
Búsqueda mejorada mediante propiedades algebraicas
2. El problema de las reinas
3. Números de Hamming
2 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Tema 11: Aplicaciones de programación funcional
1. El juego de cifras y letras
Introducción
Búsqueda de la solución por fuerza bruta
Búsqueda combinando generación y evaluación
Búsqueda mejorada mediante propiedades algebraicas
2. El problema de las reinas
3. Números de Hamming
3 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Presentación del juego
Cifras y letras es un programa de Canal Sur que incluye un juego
numérico cuya esencia es la siguiente:
Dada una sucesión de números naturales y un número objetivo,
intentar construir una expresión cuyo valor es el objetivo
combinando los números de la sucesión usando suma, resta,
multiplicación, división y paréntesis. Cada número de la sucesión
puede usarse como máximo una vez. Además, todos los números,
incluyendo los resultados intermedios tienen que ser enteros
positivos (1,2,3,. . . ).
Ejemplos
Dada la sucesión 1, 3, 7, 10, 25, 50 y el objetivo 765, una solución
es (1+50)*(25−10).
Para el problema anterior, existen 780 soluciones.
Con la sucesión anterior y el objetivo 831, no hay solución.
4 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Formalización del problema: Operaciones
Las operaciones son sumar, restar, multiplicar o dividir.
data Op = Sum | Res | Mul | Div
instance Show Op where
show Sum = "+"
show Res = "-"
show Mul = "*"
show Div = "/"
ops es la lista de las operaciones.
ops :: [Op]
ops = [Sum,Res,Mul,Div]
5 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Operaciones válidas
(valida o x y) se verifica si la operación o aplicada a los
números naturales x e y da un número natural. Por ejemplo,
valida Res 5 3 True
valida Res 3 5 False
valida Div 6 3 True
valida Div 6 4 False
valida :: Op -> Int -> Int -> Bool
valida Sum _ _ = True
valida Res x y = x > y
valida Mul _ _ = True
valida Div x y = y /= 0 && x `mod` y == 0
6 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Operaciones válidas
(valida o x y) se verifica si la operación o aplicada a los
números naturales x e y da un número natural. Por ejemplo,
valida Res 5 3 True
valida Res 3 5 False
valida Div 6 3 True
valida Div 6 4 False
valida :: Op -> Int -> Int -> Bool
valida Sum _ _ = True
valida Res x y = x > y
valida Mul _ _ = True
valida Div x y = y /= 0 && x `mod` y == 0
6 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Aplicación de operaciones
(aplica o x y) es el resultado de aplicar la operación o a los
números naturales x e y. Por ejemplo,
aplica Sum 2 3 5
aplica Div 6 3 2
aplica :: Op -> Int -> Int -> Int
aplica Sum x y = x + y
aplica Res x y = x - y
aplica Mul x y = x * y
aplica Div x y = x `div` y
7 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Aplicación de operaciones
(aplica o x y) es el resultado de aplicar la operación o a los
números naturales x e y. Por ejemplo,
aplica Sum 2 3 5
aplica Div 6 3 2
aplica :: Op -> Int -> Int -> Int
aplica Sum x y = x + y
aplica Res x y = x - y
aplica Mul x y = x * y
aplica Div x y = x `div` y
7 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Expresiones
Las expresiones son números enteros o aplicaciones de operaciones a
dos expresiones.
data Expr = Num Int | Apl Op Expr Expr
instance Show Expr where
show (Num n)
show (Apl o i d) = parentesis i ++ show o ++ parentesis d
= show n
where
parentesis (Num n) = show n
parentesis e
= "(" ++ show e ++ ")"
Ejemplo: Expresión correspondiente a (1+50)*(25−10)
ejExpr :: Expr
ejExpr = Apl Mul e1 e2
where e1 = Apl Sum (Num 1) (Num 50)
e2 = Apl Res (Num 25) (Num 10)
8 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Números de una expresión
(numeros e) es la lista de los números que aparecen en la
expresión e. Por ejemplo,
*Main> numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7))
[2,3,7]
numeros :: Expr -> [Int]
numeros (Num n)
numeros (Apl _ l r) = numeros l ++ numeros r
= [n]
9 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Números de una expresión
(numeros e) es la lista de los números que aparecen en la
expresión e. Por ejemplo,
*Main> numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7))
[2,3,7]
numeros :: Expr -> [Int]
numeros (Num n)
numeros (Apl _ l r) = numeros l ++ numeros r
= [n]
9 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Valor de una expresión
(valor e) es la lista formada por el valor de la expresión e si
todas las operaciones para calcular el valor de e son números
positivos y la lista vacía en caso contrario. Por ejemplo,
valor (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) [35]
valor (Apl Res (Apl Sum (Num 2) (Num 3)) (Num 7)) []
valor (Apl Sum (Apl Res (Num 2) (Num 3)) (Num 7)) []
valor :: Expr -> [Int]
valor (Num n)
valor (Apl o i d) = [aplica o x y | x <- valor i
, y <- valor d
, valida o x y]
= [n | n > 0]
10 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Valor de una expresión
(valor e) es la lista formada por el valor de la expresión e si
todas las operaciones para calcular el valor de e son números
positivos y la lista vacía en caso contrario. Por ejemplo,
valor (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) [35]
valor (Apl Res (Apl Sum (Num 2) (Num 3)) (Num 7)) []
valor (Apl Sum (Apl Res (Num 2) (Num 3)) (Num 7)) []
valor :: Expr -> [Int]
valor (Num n)
valor (Apl o i d) = [aplica o x y | x <- valor i
, y <- valor d
, valida o x y]
= [n | n > 0]
10 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatorias: Sublistas
(sublistas xs) es la lista de las sublistas de xs. Por ejemplo,
*Main> sublistas "bc"
["","c","b","bc"]
*Main> sublistas "abc"
["","c","b","bc","a","ac","ab","abc"]
sublistas :: [a] -> [[a]]
sublistas []
sublistas (x:xs) = yss ++ map (x:) yss
= [[]]
where yss = sublistas xs
11 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatorias: Sublistas
(sublistas xs) es la lista de las sublistas de xs. Por ejemplo,
*Main> sublistas "bc"
["","c","b","bc"]
*Main> sublistas "abc"
["","c","b","bc","a","ac","ab","abc"]
sublistas :: [a] -> [[a]]
sublistas []
sublistas (x:xs) = yss ++ map (x:) yss
= [[]]
where yss = sublistas xs
11 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatoria: Intercalado
(intercala x ys) es la lista de las listas obtenidas intercalando
x entre los elementos de ys. Por ejemplo,
intercala 'x' "bc" ["xbc","bxc","bcx"]
intercala 'x' "abc" ["xabc","axbc","abxc","abcx"]
intercala :: a -> [a] -> [[a]]
intercala x []
intercala x (y:ys) =
= [[x]]
(x:y:ys) : map (y:) (intercala x ys)
12 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatoria: Intercalado
(intercala x ys) es la lista de las listas obtenidas intercalando
x entre los elementos de ys. Por ejemplo,
intercala 'x' "bc" ["xbc","bxc","bcx"]
intercala 'x' "abc" ["xabc","axbc","abxc","abcx"]
intercala :: a -> [a] -> [[a]]
intercala x []
intercala x (y:ys) =
= [[x]]
(x:y:ys) : map (y:) (intercala x ys)
12 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatoria: Permutaciones
(permutaciones xs) es la lista de las permutaciones de xs. Por
ejemplo,
*Main> permutaciones "bc"
["bc","cb"]
*Main> permutaciones "abc"
["abc","bac","bca","acb","cab","cba"]
permutaciones :: [a] -> [[a]]
permutaciones []
permutaciones (x:xs) =
= [[]]
concat (map (intercala x) (permutaciones xs))
13 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatoria: Permutaciones
(permutaciones xs) es la lista de las permutaciones de xs. Por
ejemplo,
*Main> permutaciones "bc"
["bc","cb"]
*Main> permutaciones "abc"
["abc","bac","bca","acb","cab","cba"]
permutaciones :: [a] -> [[a]]
permutaciones []
permutaciones (x:xs) =
= [[]]
concat (map (intercala x) (permutaciones xs))
13 / 42
IM Tema 11: Aplicaciones de programación funcional
El juego de cifras y letras
Introducción
Funciones combinatoria: Elecciones
(elecciones xs) es la lista formada por todas las sublistas de
xs en cualquier orden. Por ejemplo,
*Main> elecciones "abc"
["","c","b","bc","cb","a","ac","ca","ab","ba",
"abc","bac","bca","acb","cab","cba"]
elecciones :: [a] -> [[a]]
elecciones xs =
concat (map permutaciones (sublistas xs))
14 / 42
IM Tema 11: Aplicaciones de pr
Comentarios de: Tema 11: Aplicaciones de programación funcional - Informática (2016–17) (0)
No hay comentarios