Menu Close

Mes: noviembre 2022

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"

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


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


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

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]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


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


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

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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

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


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

El tipo de los números naturales

El tipo de los números raturales se puede definir por

   data Nat = Cero | Suc Nat
     deriving (Show, Eq)

de forma que Suc (Suc (Suc Cero)) representa el número 3.

Definir las siguientes funciones

   nat2int :: Nat -> Int
   int2nat :: Int -> Nat
   suma    :: Nat -> Nat -> Nat

tales que

  • nat2int n es el número entero correspondiente al número natural n. Por ejemplo,
     nat2int (Suc (Suc (Suc Cero)))  ==  3
  • int2nat n es el número natural correspondiente al número entero n. Por ejemplo,
     int2nat 3  ==  Suc (Suc (Suc Cero))
  • suma m n es la suma de los número naturales m y n. Por ejemplo,
     λ> suma (Suc (Suc Cero)) (Suc Cero)
     Suc (Suc (Suc Cero))
     λ> nat2int (suma (Suc (Suc Cero)) (Suc Cero))
     3
     λ> nat2int (suma (int2nat 2) (int2nat 1))
     3

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Nat = Cero | Suc Nat
  deriving (Show, Eq)
 
nat2int :: Nat -> Int
nat2int Cero    = 0
nat2int (Suc n) = 1 + nat2int n
 
int2nat :: Int -> Nat
int2nat 0 = Cero
int2nat n = Suc (int2nat (n-1))
 
suma :: Nat -> Nat -> Nat
suma Cero    n = n
suma (Suc m) n = Suc (suma m n)


Soluciones en Python

from dataclasses import dataclass
 
@dataclass
class Nat:
    pass
 
@dataclass
class Cero(Nat):
    pass
 
@dataclass
class Suc(Nat):
    n: Nat
 
def nat2int(n: Nat) -> int:
    match n:
        case Cero():
            return 0
        case Suc(n):
            return 1 + nat2int(n)
    assert False
 
def int2nat(n: int) -> Nat:
    if n == 0:
        return Cero()
    return Suc(int2nat(n - 1))
 
def suma(m: Nat, n: Nat) -> Nat:
    match m:
        case Cero():
            return n
        case Suc(m):
            return Suc(suma(m, n))
    assert False

El tipo de figuras geométricas

Se consideran las figuras geométricas formadas por circulos (definidos por su radio) y rectángulos (definidos por su base y su altura). El tipo de las figura geométricas se define por

   data Figura = Circulo Float | Rect Float Float

Definir las funciones

   area     :: Figura -> Float
   cuadrado :: Float -> Figura

tales que

  • area f es el área de la figura f. Por ejemplo,
     area (Circulo 1)   ==  3.1415927
     area (Circulo 2)   ==  12.566371
     area (Rect 2 5)    ==  10.0
  • cuadrado n es el cuadrado de lado n. Por ejemplo,
     area (cuadrado 3)  ==  9.0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Figura = Circulo Float | Rect Float Float
 
area :: Figura -> Float
area (Circulo r) = pi*r^2
area (Rect x y)  = x*y
 
cuadrado :: Float -> Figura
cuadrado n = Rect n n


Soluciones en Python

from dataclasses import dataclass
from math import pi
 
@dataclass
class Figura:
    """Figuras geométricas"""
 
@dataclass
class Circulo(Figura):
    r: float
 
@dataclass
class Rect(Figura):
    x: float
    y: float
 
def area(f: Figura) -> float:
    match f:
        case Circulo(r):
            return pi * r**2
        case Rect(x, y):
            return x * y
    assert False
 
def cuadrado(n: float) -> Figura:
    return Rect(n, n)