Usando el tipo de las expresiones aritméticas, definir la función
resta :: Expr -> Expr -> Expr
tal que resta e1 e2 es la expresión correspondiente a la diferencia de e1 y e2. Por ejemplo,
resta (Lit 42) (Lit 2) == Suma (Lit 42) (Op (Lit 2))
Comprobar con QuickCheck que
valor (resta x y) == valor x - valor y
Usando el tipo de las expresiones aritméticas, definir la función
valor :: Expr -> Int
tal que valor e es el valor de la expresión e (donde el valor de SiCero e e1 e2 es el valor de e1 si el valor de e es cero y el es el valor de e2, en caso contrario). Por ejemplo,
valor (Op (Suma (Lit 3) (Lit 5))) == -8 valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4 valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5
El tipo de las expresiones aritméticas formadas por
se define como se muestra a continuación.
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show)
El tipo de las expresiones aritméticas formadas por
se define como se muestra a continuación.
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class Lit(Expr): x: int @dataclass class Suma(Expr): x: Expr y: Expr @dataclass class Op(Expr): x: Expr @dataclass class SiCero(Expr): x: Expr y: Expr z: Expr
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))
El tipo de los árboles binarios se puede definir por
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq)
Definir la función
creaArbol :: Int -> Arbol ()
tal que creaArbol n es el árbol cuyas hoyas están en la profundidad n. Por ejemplo,
λ> creaArbol 2 Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ()))
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))
El tipo de los árboles binarios se puede definir por
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq)
Definir la función
mismaForma :: Arbol a -> Arbol b -> Bool
tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,
λ> arbol1 = Hoja 5 λ> arbol2 = Hoja 3 λ> mismaForma arbol1 arbol2 True λ> arbol3 = Nodo (Hoja 6) (Hoja 7) λ> mismaForma arbol1 arbol3 False λ> arbol4 = Nodo (Hoja 9) (Hoja 5) λ> mismaForma arbol3 arbol4 True
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))
El tipo de los árboles binarios se puede definir por
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq)
Definir la función
mapArbol :: (a -> b) -> Arbol a -> Arbol b
tal que mapArbol f t es el árbolo obtenido aplicando la función f a los elementos del árbol t. Por ejemplo,
λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4)) Nodo (Hoja 3) (Hoja 5)
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))
El tipo de los árboles binarios se puede definir por
data Arbol a = Hoja a
| Nodo (Arbol a) (Arbol a)
Definir la función
altura :: Arbol a -> Int
tal que altura t es la altura del árbol t. Por ejemplo,
λ> altura (Hoja 1) 0 λ> altura (Nodo (Hoja 1) (Hoja 6)) 1 λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2)) 2 λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7))) 2
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))
usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a)
El árbol binario
· / \ / \ · · / \ / \ 1 4 6 9
se puede representar por
ejArbol = Nodo(Nodo(Hoja(1), Hoja(4)), Nodo(Hoja(6), Hoja(9)))
usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class Hoja(Arbol[A]): x: A @dataclass class Nodo(Arbol[A]): i: Arbol[A] d: Arbol[A]
Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,
(A ∧ B) → A es una tautologíaA → (A ∧ B) no es una tautologíaUsando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función
esTautologia :: FProp -> Bool
tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,
λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A')) True λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B'))) False
Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función
interpretaciones :: FProp -> [Interpretacion]
tal que interpretaciones p es la lista de las interpretaciones de la fórmula p. Por ejemplo,
λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B'))) [[('A',False),('B',False)], [('A',False),('B',True)], [('A',True),('B',False)], [('A',True),('B',True)]]