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 |
La función sustitucion se puede implementar de la siguiente manera:
La función se aplica recursivamente sobre la expresión, revisando el tipo de cada sub-expresión. Si el sub-expresión es una constante (C), se devuelve tal cual. Si es una variable (V), se busca en la lista de sustituciones (s) si existe una sustitución para esa variable. Si existe se devuelve la constante correspondiente, si no se devuelve la variable tal cual. Si el sub-expresión es una suma (S) o un producto (P), se aplica recursivamente la función sustitucion sobre ambos sub-expresiones.