PFH: La semana en Exercitium (14 de enero de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Valor de una expresión aritmética con una variable
- 2. Número de variables de una expresión aritmética
- 3. Valor de una expresión aritmética con variables
- 4. Número de sumas en una expresión aritmética
- 5. Sustitución en una expresión aritmética
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
|
1 2 3 4 |
data Expr = X | C Int | S Expr Expr | P Expr Expr |
Por ejemplo, la expresión X·(13+X) se representa por
|
1 |
P X (S (C 13) X) |
Definir la función
|
1 |
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,
|
1 |
valor (P X (S (C 13) X)) 2 == 30 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 |
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 |
|
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 |
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
|
1 2 3 4 |
data Expr = X | C Int | S Expr Expr | P Expr Expr |
Por ejemplo, la expresión X·(13+X) se representa por
|
1 |
P X (S (C 13) X) |
Definir la función
|
1 |
numVars :: Expr -> Int |
tal que numVars e es el número de variables en la expresión e. Por ejemplo,
|
1 2 3 |
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.
|
1 2 3 4 5 6 7 8 9 10 |
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 |
|
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 |
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
|
1 2 3 4 |
data Expr = C Int | V Char | S Expr Expr | P Expr Expr |
Por ejemplo, la expresión 2·(a+5) se representa por
|
1 |
P (C 2) (S (V 'a') (C 5)) |
Definir la función
|
1 |
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,
|
1 2 |
λ> 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.
|
1 2 3 4 5 6 7 8 9 10 |
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 |
|
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 |
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
|
1 2 3 4 |
data Expr = C Int | V Char | S Expr Expr | P Expr Expr |
Por ejemplo, la expresión 2·(a+5) se representa por
|
1 |
P (C 2) (S (V 'a') (C 5)) |
Definir la función
|
1 |
sumas :: Expr -> Int |
tal que sumas e es el número de sumas en la expresión e. Por ejemplo,
|
1 2 3 |
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.
|
1 2 3 4 5 6 7 8 9 10 |
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 |
|
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 |
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
|
1 2 3 4 5 |
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
|
1 |
P (C 2) (S (V 'a') (C 5)) |
Definir la función
|
1 |
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,
|
1 2 3 4 |
λ> 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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) |
|
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 40 |
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 |