Menu Close

PFH: La semana en Exercitium (3 de diciembre de 2022)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. El tipo de las listas

El tipo de las listas, con elementos de tipo a, se puede definir por

   data Lista a = Nil | Cons a (Lista a)

Por ejemplo, la lista [4,2,5] se representa por Cons 4 (Cons 2 (Cons 5 Nil)).

Definir la función

   longitud :: Lista a -> Int

tal que longitud xs es la longitud de la lista xs. Por ejemplo,

   longitud (Cons 4 (Cons 2 (Cons 5 Nil)))  ==  3

1.1. Soluciones en Haskell

data Lista a = Nil | Cons a (Lista a)
 
longitud :: Lista a -> Int
longitud Nil         = 0
longitud (Cons _ xs) = 1 + longitud xs

1.2. Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Lista(Generic[A]):
    pass
 
@dataclass
class Nil(Lista[A]):
    pass
 
@dataclass
class Cons(Lista[A]):
    x: A
    xs: Lista[A]
 
def longitud(xs: Lista[A]) -> int:
    match xs:
        case Nil():
            return 0
        case Cons(_, xs):
            return 1 + longitud(xs)
    assert False

2. El tipo de los árboles binarios

El árbol binario

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
                  5
                  (Nodo (Hoja 6) 7 (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol = Hoja Int
              | Nodo Arbol Int Arbol

Definir las funciones

   ocurre :: Int -> Arbol -> Bool
   aplana :: Arbol -> [Int]

tales que

  • ocurre m a se verifica si m ocurre en el árbol a. Por ejemplo,
     ocurre 4  ejArbol  ==  True
     ocurre 10 ejArbol  ==  False
  • aplana a es la lista obtenida aplanando el árbol a. Por ejemplo,
     aplana ejArbol  ==  [1,3,4,5,6,7,9]

2.1. Soluciones en Haskell

data Arbol = Hoja Int
           | Nodo Arbol Int Arbol
 
ejArbol :: Arbol
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
               5
               (Nodo (Hoja 6) 7 (Hoja 9))
 
ocurre :: Int -> Arbol -> Bool
ocurre m (Hoja n)     = m == n
ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d
 
aplana :: Arbol -> [Int]
aplana (Hoja n)     = [n]
aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d

2.2. Soluciones en Python

from dataclasses import dataclass
 
@dataclass
class Arbol:
    pass
 
@dataclass
class Hoja(Arbol):
    x: int
 
@dataclass
class Nodo(Arbol):
    i: Arbol
    x: int
    d: Arbol
 
ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)),
               5,
               Nodo(Hoja(6), 7, Hoja(9)))
 
def ocurre(m: int, a: Arbol) -> bool:
    match a:
        case Hoja(n):
            return m == n
        case Nodo(i, n, d):
            return m == n or ocurre(m, i) or ocurre(m, d)
    assert False
 
def aplana(a: Arbol) -> list[int]:
    match a:
        case Hoja(n):
            return [n]
        case Nodo(i, n, d):
            return aplana(i) + [n] + aplana(d)
    assert False

3. El tipo de las fórmulas proposicionales: Variables de una fórmula

El tipo de las fórmulas proposicionales se puede definir por

   data FProp = Const Bool
              | Var Char
              | Neg FProp
              | Conj FProp FProp
              | Impl FProp FProp
     deriving Show

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

Definir la función

   variables :: FProp -> [Char]

tal que variables p es la lista de las variables de la fórmula p. Por ejemplo,

   λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
   "AB"
   λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
   "AAB"

3.1. Soluciones en Haskell

data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
variables :: FProp -> [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

3.2. Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class FProp:
    pass
 
@dataclass
class Const(FProp):
    x: bool
 
@dataclass
class Var(FProp):
    x: str
 
@dataclass
class Neg(FProp):
    x: FProp
 
@dataclass
class Conj(FProp):
    x: FProp
    y: FProp
 
@dataclass
class Impl(FProp):
    x: FProp
    y: FProp
 
def variables(f: FProp) -> list[str]:
    match f:
        case Const(_):
            return []
        case Var(x):
            return [x]
        case Neg(p):
            return variables(p)
        case Conj(p, q):
            return variables(p) + variables(q)
        case Impl(p, q):
            return variables(p) + variables(q)
    assert False

4. El tipo de las fórmulas proposicionales: Valor de una fórmula

El tipo de las fórmulas proposicionales se puede definir por

   data FProp = Const Bool
              | Var Char
              | Neg FProp
              | Conj FProp FProp
              | Impl FProp FProp
     deriving Show

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por

   [('A', True), ('B', False)]

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

El valor de una fórmula en una interpretación se calcula usando las funciones de verdad de las conectivas que se muestran a continuación

   |---+----|   |---+---+-------+-------|
   | p | ¬p |   | p | q | p ∧ q | p → q |
   |---+----|   |---+---+-------+-------|
   | T | F  |   | T | T | T     | T     |
   | F | T  |   | T | F | F     | F     |
   |---+----|   | F | T | F     | T     |
                | F | F | F     | T     |
                |---+---+-------+-------|

Definir la función

   valor :: Interpretacion -> FProp -> Bool

tal que valor i p es el valor de la fórmula p en la interpretación i. Por ejemplo,

   λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
   λ> valor [('A',False),('B',False)] p
   True
   λ> valor [('A',True),('B',False)] p
   False

4.1. Soluciones en Haskell

data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
type Interpretacion = [(Char, Bool)]
 
valor :: Interpretacion -> FProp -> 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
 
-- (busca c t) es el valor del primer elemento de la lista de asociación
-- t cuya clave es c. Por ejemplo,
--    busca 2 [(1,'a'),(3,'d'),(2,'c')]  ==  'c'
busca :: Eq c => c -> [(c,v)] -> v
busca c t = head [v | (c',v) <- t, c == c']

4.2. Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class FProp:
    pass
 
@dataclass
class Const(FProp):
    x: bool
 
@dataclass
class Var(FProp):
    x: str
 
@dataclass
class Neg(FProp):
    x: FProp
 
@dataclass
class Conj(FProp):
    x: FProp
    y: FProp
 
@dataclass
class Impl(FProp):
    x: FProp
    y: FProp
 
Interpretacion = list[tuple[str, bool]]
 
# busca(c, t) es el valor del primer elemento de la lista de asociación
# t cuya clave es c. Por ejemplo,
#    >>> busca('B', [('A', True), ('B', False), ('C', True)])
#    False
def busca(c: str, i: Interpretacion) -> bool:
    return [v for (d, v) in i if d == c][0]
 
def valor(i: Interpretacion, f: FProp) -> bool:
    match f:
        case Const(b):
            return b
        case Var(x):
            return busca(x, i)
        case Neg(p):
            return not valor(i, p)
        case Conj(p, q):
            return valor(i, p) and valor(i, q)
        case Impl(p, q):
            return valor(i, p) <= valor(i, q)
    assert False

5. El tipo de las fórmulas proposicionales: Interpretaciones de una fórmula

El tipo de las fórmulas proposicionales se puede definir por

   data FProp = Const Bool
              | Var Char
              | Neg FProp
              | Conj FProp FProp
              | Impl FProp FProp
     deriving Show

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por

   [('A', True), ('B', False)]

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

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)]]

5.1. Soluciones en Haskell

import Data.List (nub)
 
data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
type Interpretacion = [(Char, Bool)]
 
interpretaciones :: FProp -> [Interpretacion]
interpretaciones p =
  [zip vs i | i <- interpretacionesVar (length vs)]
  where vs = nub (variables p)
 
-- (interpretacionesVar n) es la lista de las interpretaciones de n
-- variables. Por ejemplo,
--    λ> interpretacionesVar 2
--    [[False,False],
--     [False,True],
--     [True,False],
--     [True,True]]
interpretacionesVar :: Int -> [[Bool]]
interpretacionesVar 0 = [[]]
interpretacionesVar n = map (False:) bss ++ map (True:) bss
  where bss = interpretacionesVar (n-1)
 
-- (variables p) es la lista de las variables de la fórmula p. Por
-- ejemplo,
--    λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
--    "AB"
--    λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
--    "AAB"
variables :: FProp -> [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

5.2. Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class FProp:
    pass
 
@dataclass
class Const(FProp):
    x: bool
 
@dataclass
class Var(FProp):
    x: str
 
@dataclass
class Neg(FProp):
    x: FProp
 
@dataclass
class Conj(FProp):
    x: FProp
    y: FProp
 
@dataclass
class Impl(FProp):
    x: FProp
    y: FProp
 
Interpretacion = list[tuple[str, bool]]
 
# variables(p) es la lista de las variables de la fórmula p. Por
# ejemplo,
#    >>> variables (Impl(Var('A'), Conj(Const(False), Neg (Var('B')))))
#    ['A', 'B']
#    >>> variables (Impl(Var('A'), Conj(Var('A'), Neg (Var('B')))))
#    ['A', 'A', 'B']
def variables(f: FProp) -> list[str]:
    match f:
        case Const(_):
            return []
        case Var(x):
            return [x]
        case Neg(p):
            return variables(p)
        case Conj(p, q):
            return variables(p) + variables(q)
        case Impl(p, q):
            return variables(p) + variables(q)
    assert False
 
# interpretacionesVar(n) es la lista de las interpretaciones de n
# variables. Por ejemplo,
#    >>> interpretacionesVar 2
#    [[False, False],
#     [False, True],
#     [True, False],
#     [True, True]]
def interpretacionesVar(n: int) -> list[list[bool]]:
    if n == 0:
        return [[]]
    bss = interpretacionesVar(n-1)
    return [[False] + x for x in bss] + [[True] + x for x in bss]
 
def interpretaciones(f: FProp) -> list[Interpretacion]:
    vs = list(set(variables(f)))
    return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]
PFH