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 |