I1M2013: Definiciones de tipos de datos en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado las definiciones de nuevos tipos de datos y de funciones sobre dichos tipos. Concretamente, se ha estudiado
- 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, las listas y los árboles.
Se ha insistido en la metodología de definición de funciones recursivas sobre tipos de datos escribiendo una ecuación por cada uno de los constructores del tipo de dato.
Como caso de estudio se ha iniciado la construcción de un programa para determinar si una fórmula es una tautología. Para ello se ha definido el tipo de dato de las fórmulas proposicionales, el de las interpretaciones y una función para definir el valor de una fórmula respecto de una interpretación. Se ha dejado como ejercicio la definición de las restantes funciones para completar el programa.
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 |
-- 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 = [(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 |
Las transparencias usadas en la clase son las páginas 1 a 23 del tema 9: