Tipos de datos algebraicos

Evaluación de árboles de expresiones aritméticas

PorJosé A. Alonso 27-noviembre-201425-abril-2021

Enunciado

-- Las expresiones aritméticas se pueden representar como árboles con
-- números en las hojas y operaciones en los nodos. Por ejemplo, la
-- expresión "9-2*4" se puede representar por el árbol
--      - 
--     / \
--    9   *
--       / \
--      2   4
-- 
-- Definiendo el tipo de dato Arbol por 
--    data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol
-- la representación del árbol anterior es
--    N (-) (H 9) (N (*) (H 2) (H 4))
--
-- Definir la función
--    valor :: Arbol -> Int
-- tal que (valor a) es el valor de la expresión aritmética
-- correspondiente al árbol a. Por ejemplo,
--    valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1
--    valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17
--    valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11
--    valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13

-- Las expresiones aritméticas se pueden representar como árboles con

-- números en las hojas y operaciones en los nodos. Por ejemplo, la

-- expresión "9-2*4" se puede representar por el árbol

-- -

-- / \

-- 9 *

-- / \

-- 2 4

-- Definiendo el tipo de dato Arbol por

-- data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

-- la representación del árbol anterior es

-- N (-) (H 9) (N (*) (H 2) (H 4))

-- Definir la función

-- valor :: Arbol -> Int

-- tal que (valor a) es el valor de la expresión aritmética

-- correspondiente al árbol a. Por ejemplo,

-- valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1

-- valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17

-- valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11

-- valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13

Soluciones

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int
valor (H x)     = x
valor (N f i d) = f (valor i) (valor d)

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int

valor (H x) = x

valor (N f i d) = f (valor i) (valor d)

Sustitución en una expresión

PorJosé A. Alonso 24-julio-201427-diciembre-2014

Enunciado

-- La expresiones aritméticas se pueden representar mediante el
-- siguiente tipo  
--    data Expr = V Char 
--              | N Int 
--              | S Expr Expr
--              | P Expr Expr
--              deriving Show
-- por ejemplo, representa la expresión "z*(3+x)" se representa por
-- (P (V 'z') (S (N 3) (V 'x'))). 
--
-- 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, 
--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'x'))) [('x',7),('z',9)]
--    P (N 9) (S (N 3) (N 7))
--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'y'))) [('x',7),('z',9)]
--    P (N 9) (S (N 3) (V 'y'))

-- La expresiones aritméticas se pueden representar mediante el

-- siguiente tipo

-- data Expr = V Char

-- | N Int

-- | S Expr Expr

-- | P Expr Expr

-- deriving Show

-- por ejemplo, representa la expresión "z*(3+x)" se representa por

-- (P (V 'z') (S (N 3) (V 'x'))).

-- 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,

-- ghci> sustitucion (P (V 'z') (S (N 3) (V 'x'))) [('x',7),('z',9)]

-- P (N 9) (S (N 3) (N 7))

-- ghci> sustitucion (P (V 'z') (S (N 3) (V 'y'))) [('x',7),('z',9)]

-- P (N 9) (S (N 3) (V 'y'))

Soluciones

data Expr = V Char 
          | N Int 
          | S Expr Expr
          | P Expr Expr
          deriving Show

sustitucion :: Expr -> [(Char, Int)] -> Expr
sustitucion e [] = e
sustitucion (V c) ((d,n):ps) | c == d = N n
                             | otherwise = sustitucion (V c) ps
sustitucion (N n) _ = N 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)

data Expr = V Char

| N Int

| S Expr Expr

| P Expr Expr

deriving Show

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

sustitucion e [] = e

sustitucion (V c) ((d,n):ps) | c == d = N n

| otherwise = sustitucion (V c) ps

sustitucion (N n) _ = N 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)

Renombramiento de un árbol

PorJosé A. Alonso 3-julio-201427-diciembre-2014

-- Los árboles binarios se pueden representar mediante el tipo Arbol definido
-- por
--    data Arbol a = H a 
--                 | N a (Arbol a) (Arbol a)
--                 deriving Show
-- Por ejemplo, el árbol
--         "C"
--         / \ 
--        /   \
--       /     \
--     "B"     "A"
--     / \     / \
--   "A" "B" "B" "C" 
-- se puede definir por 
--    ej1 :: Arbol String
--    ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))
--
-- Definir la función
--    renombraArbol :: Arbol t -> Arbol Int
-- tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor
-- de los nodos y hojas por números tales que tengan el mismo valor si y
-- sólo si coincide su contenido. Por ejemplo,
--    ghci> renombraArbol ej1
--    N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))
-- Gráficamente, 
--          2 
--         / \ 
--        /   \
--       /     \
--      1       0 
--     / \     / \
--    0   1   1   2

-- Los árboles binarios se pueden representar mediante el tipo Arbol definido

-- por

-- data Arbol a = H a

-- | N a (Arbol a) (Arbol a)

-- deriving Show

-- Por ejemplo, el árbol

-- "C"

-- / \

-- "B" "A"

-- / \ / \

-- "A" "B" "B" "C"

-- se puede definir por

-- ej1 :: Arbol String

-- ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

-- Definir la función

-- renombraArbol :: Arbol t -> Arbol Int

-- tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor

-- de los nodos y hojas por números tales que tengan el mismo valor si y

-- sólo si coincide su contenido. Por ejemplo,

-- ghci> renombraArbol ej1

-- N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))

-- Gráficamente,

-- 2

-- / \

-- 1 0

-- / \ / \

-- 0 1 1 2

Soluciones

import Data.List 

data Arbol a = H a
             | N a (Arbol a) (Arbol a) 
             deriving (Show, Eq)

ej1 :: Arbol String
ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

renombraArbol :: Ord t => Arbol t -> Arbol Int
renombraArbol a = aux a
    where ys            = valores a
          aux (H x)     = H (posicion x ys)
          aux (N x i d) = N (posicion x ys) (aux i) (aux d) 

-- (valores a) es la lista de los valores en los nodos y las hojas del
-- árbol a. Por ejemplo,
--    valores ej1  ==  ["A","B","C"]
valores :: Ord a => Arbol a -> [a]
valores a = sort (nub (aux a))
    where aux (H x)     = [x]
          aux (N x i d) = x : (aux i ++ aux d)

-- (posicion x ys) es la posición de x en ys. Por ejemplo.
--    posicion 7 [5,3,7,8]  ==  2
posicion :: Eq a => a -> [a] -> Int
posicion x ys = head [n | (y,n) <- zip ys [0..], y == x]

import Data.List

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

ej1 :: Arbol String

ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

renombraArbol :: Ord t => Arbol t -> Arbol Int

renombraArbol a = aux a

where ys = valores a

aux (H x) = H (posicion x ys)

aux (N x i d) = N (posicion x ys) (aux i) (aux d)

-- (valores a) es la lista de los valores en los nodos y las hojas del

-- árbol a. Por ejemplo,

-- valores ej1 == ["A","B","C"]

valores :: Ord a => Arbol a -> [a]

valores a = sort (nub (aux a))

where aux (H x) = [x]

aux (N x i d) = x : (aux i ++ aux d)

-- (posicion x ys) es la posición de x en ys. Por ejemplo.

-- posicion 7 [5,3,7,8] == 2

posicion :: Eq a => a -> [a] -> Int

posicion x ys = head [n | (y,n) <- zip ys [0..], y == x]

Evaluación de árboles de expresiones aritméticas

Enunciado

Soluciones

Sustitución en una expresión

Enunciado

Soluciones

Renombramiento de un árbol

Soluciones

Entradas recientes

Buscar

Correo electrónico