I1M2014: Definiciones de tipos y clases en Haskell
En clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado la definición de nuevos tipos de datos y de funciones sobre dichos tipos. Concretamente, se ha visto
- cómo definir tipos usando type,
- cómo definir funciones con dominio o rango en tipos definidos usando type,
- cómo definir tipos usando data,
- cómo definir funciones con dominio o rango en tipos definidos usando data y
- cómo definir tipos de datos recursivos usando como ejemplo los naturales, los árboles y las fórmulas proposicionales.
Como caso de estudio, se ha explicado cómo construir un programa para determinar si una fórmula es una tautología.
El código correspondiente es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
-- Las fórmulas proposicionales se definen por: -- * Las constantes booleanas son fórmulas proposicionales. -- * Las fórmulas atómicas son fórmulas proposicionales. -- * Si F es una fómula proposicional, entonces -F también los es. -- * Si F y F son fórmulas proposicionales, entonces (F /\ G) y -- (F -> G) también lo son. data Prop = Const Bool | Var Char | Neg Prop | Conj Prop Prop | Impl Prop Prop deriving Show -- Ejemplos de representación de fórmulas proposicionales: Las fórmulas -- * p1 := A /\ -A -- * p2 := (A /\ B) -> A -- * p3 := A -> (A /\ B) -- * p4 := (A -> (A -> B)) -> B -- se representan por p1, p2, p3, p4 :: Prop p1 = Conj (Var 'A') (Neg (Var 'A')) p2 = Impl (Conj (Var 'A') (Var 'B')) (Var 'A') p3 = Impl (Var 'A') (Conj (Var 'A') (Var 'B')) p4 = Impl (Conj (Var 'A') (Impl (Var 'A') (Var 'B'))) (Var 'B') -- Las interpretaciones son listas formadas por el nombre de una -- variable proposicional y un valor de verdad. type Interpretacion = Asoc Char Bool -- (valor i p) es el valor de la proposición p en la interpretación -- i. Por ejemplo, -- valor [('A',False),('B',True)] p3 => True -- valor [('A',True),('B',False)] p3 => False valor :: Interpretacion -> Prop -> Bool valor _ (Const b) = b valor i (Var x) = busca x i valor i (Neg p) = not (valor i p) valor i (Conj p q) = valor i p && valor i q valor i (Impl p q) = valor i p <= valor i q -- (variables p) es la lista de los nombres de las variables de la -- fórmula p. Por ejemplo, -- variables p3 == "AAB" variables :: Prop -> [Char] variables (Const _) = [] variables (Var x) = [x] variables (Neg p) = variables p variables (Conj p q) = variables p ++ variables q variables (Impl p q) = variables p ++ variables q -- (interpretacionesVar n) es la lista de las interpretaciones con n -- variables. Por ejemplo, -- *Main> interpretacionesVar 2 -- [[False,False], -- [False,True], -- [True,False], -- [True,True]] interpretacionesVar :: Int -> [[Bool]] interpretacionesVar 0 = [[]] interpretacionesVar (n+1) = map (False:) bss ++ map (True:) bss where bss = interpretacionesVar n -- (interpretaciones p) es la lista de las interpretaciones de la -- fórmula p. Por ejemplo, -- *Main> interpretaciones p3 -- [[('A',False),('B',False)], -- [('A',False),('B',True)], -- [('A',True),('B',False)], -- [('A',True),('B',True)]] interpretaciones :: Prop -> [Interpretacion] interpretaciones p = map (zip vs) (interpretacionesVar (length vs)) where vs = nub (variables p) -- Una definición alternativa es interpretaciones2 :: Prop -> [Interpretacion] interpretaciones2 p = [zip vs i | i <- is] where vs = nub (variables p) is = (interpretacionesVar (length vs)) -- (esTautologia p) se verifica si la fórmula p es una tautología. Por -- ejemplo, -- esTautologia p1 => False -- esTautologia p2 => True -- esTautologia p3 => False -- esTautologia p4 => True esTautologia :: Prop -> Bool esTautologia p = and [valor i p | i <- interpretaciones p] |
Finalmente, se ha explicado cómo definir clases en Haskell.
Las transparencias usadas en la clase son las del tema 9: