Menu Close

PFH: La semana en Exercitium (14 de enero de 2023)

José A. Alonso-

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

A continuación se muestran las soluciones.

1. Valor de una expresión aritmética con una variable

Las expresiones aritméticas construidas con una variable (denotada por X), los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Expr definido por

   data Expr = X
             | C Int
             | S Expr Expr
             | P Expr Expr

Por ejemplo, la expresión X·(13+X) se representa por

   P X (S (C 13) X)

Definir la función

   valor :: Expr -> Int -> Int

tal que valor e n es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

   valor (P X (S (C 13) X)) 2  ==  30

Soluciones

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


Soluciones en Haskell

data Expr = X
          | C Int
          | S Expr Expr
          | P Expr Expr
 
valor :: Expr -> Int -> Int
valor X         n = n
valor (C a)     _ = a
valor (S e1 e2) n = valor e1 n + valor e2 n
valor (P e1 e2) n = valor e1 n * valor e2 n


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class X(Expr):
    pass
 
@dataclass
class C(Expr):
    x: int
 
@dataclass
class S(Expr):
    x: Expr
    y: Expr
 
@dataclass
class P(Expr):
    x: Expr
    y: Expr
 
def valor(e: Expr, n: int) -> int:
    match e:
        case X():
            return n
        case C(a):
            return a
        case S(e1, e2):
            return valor(e1, n) + valor(e2, n)
        case P(e1, e2):
            return valor(e1, n) * valor(e2, n)
    assert False

2. Número de variables de una expresión aritmética

Las expresiones aritméticas construidas con una variable (denotada por X), los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Expr definido por

   data Expr = X
             | C Int
             | S Expr Expr
             | P Expr Expr

Por ejemplo, la expresión X·(13+X) se representa por

   P X (S (C 13) X)

Definir la función

   numVars :: Expr -> Int

tal que numVars e es el número de variables en la expresión e. Por ejemplo,

   numVars (C 3)               ==  0
   numVars X                   ==  1
   numVars (P X (S (C 13) X))  ==  2

Soluciones

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


Soluciones en Haskell

data Expr = X
          | C Int
          | S Expr Expr
          | P Expr Expr
 
numVars :: Expr -> Int
numVars X       = 1
numVars (C _)   = 0
numVars (S a b) = numVars a + numVars b
numVars (P a b) = numVars a + numVars b


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class X(Expr):
    pass
 
@dataclass
class C(Expr):
    x: int
 
@dataclass
class S(Expr):
    x: Expr
    y: Expr
 
@dataclass
class P(Expr):
    x: Expr
    y: Expr
 
def numVars(e: Expr) -> int:
    match e:
        case X():
            return 1
        case C(_):
            return 0
        case S(e1, e2):
            return numVars(e1) + numVars(e2)
        case P(e1, e2):
            return numVars(e1) + numVars(e2)
    assert False

3. Valor de una expresión aritmética con variables

Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos

   data Expr = C Int
             | V Char
             | S Expr Expr
             | P Expr Expr

Por ejemplo, la expresión 2·(a+5) se representa por

   P (C 2) (S (V 'a') (C 5))

Definir la función

   valor :: Expr -> [(Char,Int)] -> Int

tal que valor x e es el valor de la expresión x en el entorno e (es decir, el valor de la expresión donde las variables de x se sustituyen por los valores según se indican en el entorno e). Por ejemplo,

   λ> valor (P (C 2) (S (V 'a') (V 'b'))) [('a',2),('b',5)]
   14

Soluciones

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


Soluciones en Haskell

data Expr = C Int
          | V Char
          | S Expr Expr
          | P Expr Expr
 
valor :: Expr -> [(Char,Int)] -> Int
valor (C x)   _ = x
valor (V x)   e = head [y | (z,y) <- e, z == x]
valor (S x y) e = valor x e + valor y e
valor (P x y) e = valor x e * valor y e


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class C(Expr):
    x: int
 
@dataclass
class V(Expr):
    x: str
 
@dataclass
class S(Expr):
    x: Expr
    y: Expr
 
@dataclass
class P(Expr):
    x: Expr
    y: Expr
 
def valor(e: Expr, xs: list[tuple[str, int]]) -> int:
    match e:
        case C(a):
            return a
        case V(x):
            return [y for (z, y) in xs if z == x][0]
        case S(e1, e2):
            return valor(e1, xs) + valor(e2, xs)
        case P(e1, e2):
            return valor(e1, xs) * valor(e2, xs)
    assert False

4. Número de sumas en una expresión aritmética

Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos

   data Expr = C Int
             | V Char
             | S Expr Expr
             | P Expr Expr

Por ejemplo, la expresión 2·(a+5) se representa por

   P (C 2) (S (V 'a') (C 5))

Definir la función

   sumas :: Expr -> Int

tal que sumas e es el número de sumas en la expresión e. Por ejemplo,

   sumas (P (V 'z') (S (C 3) (V 'x')))  ==  1
   sumas (S (V 'z') (S (C 3) (V 'x')))  ==  2
   sumas (P (V 'z') (P (C 3) (V 'x')))  ==  0

Soluciones

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


Soluciones en Haskell

data Expr = C Int
          | V Char
          | S Expr Expr
          | P Expr Expr
 
sumas :: Expr -> Int
sumas (V _)   = 0
sumas (C _)   = 0
sumas (S x y) = 1 + sumas x + sumas y
sumas (P x y) = sumas x + sumas y


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class C(Expr):
    x: int
 
@dataclass
class V(Expr):
    x: str
 
@dataclass
class S(Expr):
    x: Expr
    y: Expr
 
@dataclass
class P(Expr):
    x: Expr
    y: Expr
 
def sumas(e: Expr) -> int:
    match e:
        case C(a):
            return 0
        case V(x):
            return 0
        case S(e1, e2):
            return 1 + sumas(e1) + sumas(e2)
        case P(e1, e2):
            return sumas(e1) + sumas(e2)
    assert False

5. Sustitución en una expresión aritmética

Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos

   data Expr = C Int
             | V Char
             | S Expr Expr
             | P Expr Expr
     deriving (Eq, Show)

Por ejemplo, la expresión 2·(a+5) se representa por

   P (C 2) (S (V 'a') (C 5))

Definir la función

   sustitucion :: Expr -> [(Char, Int)] -> Expr

tal que sustitucion e s es la expresión obtenida sustituyendo las variables de la expresión e según se indica en la sustitución s. Por ejemplo,

   λ> sustitucion (P (V 'z') (S (C 3) (V 'x'))) [('x',7),('z',9)]
   P (C 9) (S (C 3) (C 7))
   λ> sustitucion (P (V 'z') (S (C 3) (V 'y'))) [('x',7),('z',9)]
   P (C 9) (S (C 3) (V 'y'))

Soluciones

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


Soluciones en Haskell

data Expr = C Int
          | V Char
          | S Expr Expr
          | P Expr Expr
  deriving (Eq, Show)
 
sustitucion :: Expr -> [(Char, Int)] -> Expr
sustitucion e []          = e
sustitucion (V c) ((d,n):ps)
  | c == d                = C n
  | otherwise             = sustitucion (V c) ps
sustitucion (C n) _      = C n
sustitucion (S e1 e2) ps = S (sustitucion e1 ps) (sustitucion e2 ps)
sustitucion (P e1 e2) ps = P (sustitucion e1 ps) (sustitucion e2 ps)


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class C(Expr):
    x: int
 
@dataclass
class V(Expr):
    x: str
 
@dataclass
class S(Expr):
    x: Expr
    y: Expr
 
@dataclass
class P(Expr):
    x: Expr
    y: Expr
 
def sustitucion(e: Expr, ps: list[tuple[str, int]]) -> Expr:
    match (e, ps):
        case(e, []):
            return e
        case (V(c), ps):
            if c == ps[0][0]:
                return C(ps[0][1])
            return sustitucion(V(c), ps[1:])
        case (C(n), _):
            return C(n)
        case (S(e1, e2), ps):
            return S(sustitucion(e1, ps), sustitucion(e2, ps))
        case (P(e1, e2), ps):
            return P(sustitucion(e1, ps), sustitucion(e2, ps))
    assert False
PFH