Exercitium

TAD de las pilas: Transformaciones entre pilas y listas

PorJosé A. Alonso 23-enero-202322-enero-2023

Utilizando el tipo abstracto de datos de las pilas, definir las funciones

   listaApila :: [a] -> Pila a
   pilaAlista :: Pila a -> [a]

1 2	listaApila :: [a] -> Pila a pilaAlista :: Pila a -> [a]

tales que

listaApila xs es la pila formada por los elementos de xs. Por ejemplo,

     λ> listaApila [3, 2, 5]
     5 | 2 | 3

1 2	λ> listaApila [3, 2, 5] 5 \| 2 \| 3

pilaAlista p es la lista formada por los elementos de la pila p. Por ejemplo,

     λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))
     [3, 2, 5]

1 2	λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) [3, 2, 5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   pilaAlista (listaApila xs) == xs
   listaApila (pilaAlista p)  == p

1 2	pilaAlista (listaApila xs) == xs listaApila (pilaAlista p) == p

Soluciones

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

Soluciones en Haskell

module Transformaciones_pilas_listas where

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Test.QuickCheck

-- 1ª definición de listaApila
-- ===========================

listaApila :: [a] -> Pila a
listaApila ys = aux (reverse ys)
  where aux []     = vacia
        aux (x:xs) = apila x (aux xs)

-- 2ª definición de listaApila
-- ===========================

listaApila2 :: [a] -> Pila a
listaApila2 = aux . reverse
  where aux [] = vacia
        aux (x:xs) = apila x (aux xs)

-- 3ª definición de listaApila
-- ===========================

listaApila3 :: [a] -> Pila a
listaApila3 = aux . reverse
  where aux = foldr apila vacia

-- 4ª definición de listaApila
-- ===========================

listaApila4 :: [a] -> Pila a
listaApila4 xs = foldr apila vacia (reverse xs)

-- 5ª definición de listaApila
-- ===========================

listaApila5 :: [a] -> Pila a
listaApila5 = foldr apila vacia . reverse

-- Comprobación de equivalencia de las definiciones de listaApila
-- ==============================================================

-- La propiedad es
prop_listaApila :: [Int] -> Bool
prop_listaApila xs =
  all (== listaApila xs)
      [listaApila2 xs,
       listaApila3 xs,
       listaApila4 xs,
       listaApila5 xs]

-- La comprobación es
--    λ> quickCheck prop_listaApila
--    +++ OK, passed 100 tests.

-- 1ª definición de pilaAlista
-- ===========================

pilaAlista :: Pila a -> [a]
pilaAlista p
  | esVacia p = []
  | otherwise = pilaAlista dp ++ [cp]
  where cp = cima p
        dp = desapila p

-- 2ª definición de pilaAlista
-- ===========================

pilaAlista2 :: Pila a -> [a]
pilaAlista2 = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p

-- Comprobación de equivalencia de las definiciones de pilaAlista
-- ==============================================================

-- La propiedad es
prop_pilaAlista :: Pila Int -> Bool
prop_pilaAlista p =
  pilaAlista p == pilaAlista2 p

-- La comprobación es
--    λ> quickCheck prop_pilaAlista
--    +++ OK, passed 100 tests.

-- Comprobación de las propiedades
-- ===============================

-- La primera propiedad es
prop_1_listaApila :: [Int] -> Bool
prop_1_listaApila xs =
  pilaAlista (listaApila xs) == xs

-- La comprobación es
--    λ> quickCheck prop_1_listaApila
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_2_listaApila :: Pila Int -> Bool
prop_2_listaApila p =
  listaApila (pilaAlista p) == p

-- La comprobación es
--    λ> quickCheck prop_2_listaApila
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

module Transformaciones_pilas_listas where

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)

import Test.QuickCheck

-- 1ª definición de listaApila

-- ===========================

listaApila :: [a] -> Pila a

listaApila ys = aux (reverse ys)

where aux [] = vacia

aux (x:xs) = apila x (aux xs)

-- 2ª definición de listaApila

-- ===========================

listaApila2 :: [a] -> Pila a

listaApila2 = aux . reverse

where aux [] = vacia

aux (x:xs) = apila x (aux xs)

-- 3ª definición de listaApila

-- ===========================

listaApila3 :: [a] -> Pila a

listaApila3 = aux . reverse

where aux = foldr apila vacia

-- 4ª definición de listaApila

-- ===========================

listaApila4 :: [a] -> Pila a

listaApila4 xs = foldr apila vacia (reverse xs)

-- 5ª definición de listaApila

-- ===========================

listaApila5 :: [a] -> Pila a

listaApila5 = foldr apila vacia . reverse

-- Comprobación de equivalencia de las definiciones de listaApila

-- ==============================================================

-- La propiedad es

prop_listaApila :: [Int] -> Bool

prop_listaApila xs =

all (== listaApila xs)

[listaApila2 xs,

listaApila3 xs,

listaApila4 xs,

listaApila5 xs]

-- La comprobación es

-- λ> quickCheck prop_listaApila

-- +++ OK, passed 100 tests.

-- 1ª definición de pilaAlista

-- ===========================

pilaAlista :: Pila a -> [a]

pilaAlista p

| esVacia p = []

| otherwise = pilaAlista dp ++ [cp]

where cp = cima p

dp = desapila p

-- 2ª definición de pilaAlista

-- ===========================

pilaAlista2 :: Pila a -> [a]

pilaAlista2 = reverse . aux

where aux p | esVacia p = []

| otherwise = cp : aux dp

where cp = cima p

dp = desapila p

-- Comprobación de equivalencia de las definiciones de pilaAlista

-- ==============================================================

-- La propiedad es

prop_pilaAlista :: Pila Int -> Bool

prop_pilaAlista p =

pilaAlista p == pilaAlista2 p

-- La comprobación es

-- λ> quickCheck prop_pilaAlista

-- +++ OK, passed 100 tests.

-- Comprobación de las propiedades

-- ===============================

-- La primera propiedad es

prop_1_listaApila :: [Int] -> Bool

prop_1_listaApila xs =

pilaAlista (listaApila xs) == xs

-- La comprobación es

-- λ> quickCheck prop_1_listaApila

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaApila :: Pila Int -> Bool

prop_2_listaApila p =

listaApila (pilaAlista p) == p

-- La comprobación es

-- λ> quickCheck prop_2_listaApila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)

A = TypeVar('A')

# 1ª definición de listaApila
# ===========================

def listaApila(ys: list[A]) -> Pila[A]:
    def aux(xs: list[A]) -> Pila[A]:
        if not xs:
            return vacia()
        return apila(xs[0], aux(xs[1:]))

    return aux(list(reversed(ys)))

# 2ª solución de listaApila
# =========================

def listaApila2(xs: list[A]) -> Pila[A]:
    p: Pila[A] = Pila()
    for x in xs:
        p.apila(x)
    return p

# Comprobación de equivalencia de las definiciones de listaApila
# ==============================================================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaApila(xs: list[int]) -> None:
    assert listaApila(xs) == listaApila2(xs)

# 1ª definición de pilaAlista
# ===========================

def pilaAlista(p: Pila[A]) -> list[A]:
    if esVacia(p):
        return []
    cp = cima(p)
    dp = desapila(p)
    return pilaAlista(dp) + [cp]

# 2ª definición de pilaAlista
# ===========================

def pilaAlista2Aux(p: Pila[A]) -> list[A]:
    if p.esVacia():
        return []
    cp = p.cima()
    p.desapila()
    return pilaAlista2Aux(p) + [cp]

def pilaAlista2(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista2Aux(p1)

# 3ª definición de pilaAlista
# ===========================

def pilaAlista3Aux(p: Pila[A]) -> list[A]:
    r = []
    while not p.esVacia():
        r.append(p.cima())
        p.desapila()
    return r[::-1]

def pilaAlista3(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista3Aux(p1)

# Comprobación de equivalencia de las definiciones de pilaAlista
# ==============================================================

@given(p=pilaAleatoria())
def test_pilaAlista(p: Pila[int]) -> None:
    assert pilaAlista(p) == pilaAlista2(p)
    assert pilaAlista(p) == pilaAlista3(p)

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaApila(xs: list[int]) -> None:
    assert pilaAlista(listaApila(xs)) == xs

# La segunda propiedad es
@given(p=pilaAleatoria())
def test_2_listaApila(p: Pila[int]) -> None:
    assert listaApila(pilaAlista(p)) == p

# La comprobación es
#      src> poetry run pytest -v transformaciones_pilas_listas.py
#      test_listaApila PASSED
#      test_pilaAlista PASSED
#      test_1_listaApila PASSED
#      test_2_listaApila PASSED

100

101

102

103

104

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,

vacia)

A = TypeVar('A')

# 1ª definición de listaApila

# ===========================

def listaApila(ys: list[A]) -> Pila[A]:

def aux(xs: list[A]) -> Pila[A]:

if not xs:

return vacia()

return apila(xs[0], aux(xs[1:]))

return aux(list(reversed(ys)))

# 2ª solución de listaApila

# =========================

def listaApila2(xs: list[A]) -> Pila[A]:

p: Pila[A] = Pila()

for x in xs:

p.apila(x)

return p

# Comprobación de equivalencia de las definiciones de listaApila

# ==============================================================

# La propiedad es

@given(st.lists(st.integers()))

def test_listaApila(xs: list[int]) -> None:

assert listaApila(xs) == listaApila2(xs)

# 1ª definición de pilaAlista

# ===========================

def pilaAlista(p: Pila[A]) -> list[A]:

if esVacia(p):

return []

cp = cima(p)

dp = desapila(p)

return pilaAlista(dp) + [cp]

# 2ª definición de pilaAlista

# ===========================

def pilaAlista2Aux(p: Pila[A]) -> list[A]:

if p.esVacia():

return []

cp = p.cima()

p.desapila()

return pilaAlista2Aux(p) + [cp]

def pilaAlista2(p: Pila[A]) -> list[A]:

p1 = deepcopy(p)

return pilaAlista2Aux(p1)

# 3ª definición de pilaAlista

# ===========================

def pilaAlista3Aux(p: Pila[A]) -> list[A]:

r = []

while not p.esVacia():

r.append(p.cima())

p.desapila()

return r[::-1]

def pilaAlista3(p: Pila[A]) -> list[A]:

p1 = deepcopy(p)

return pilaAlista3Aux(p1)

# Comprobación de equivalencia de las definiciones de pilaAlista

# ==============================================================

@given(p=pilaAleatoria())

def test_pilaAlista(p: Pila[int]) -> None:

assert pilaAlista(p) == pilaAlista2(p)

assert pilaAlista(p) == pilaAlista3(p)

# Comprobación de las propiedades

# ===============================

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaApila(xs: list[int]) -> None:

assert pilaAlista(listaApila(xs)) == xs

# La segunda propiedad es

@given(p=pilaAleatoria())

def test_2_listaApila(p: Pila[int]) -> None:

assert listaApila(pilaAlista(p)) == p

# La comprobación es

# src> poetry run pytest -v transformaciones_pilas_listas.py

# test_listaApila PASSED

# test_pilaAlista PASSED

# test_1_listaApila PASSED

# test_2_listaApila PASSED

El tipo abstracto de datos de las pilas

PorJosé A. Alonso 20-enero-202330-enero-2023

1. El tipo abstracto de datos de las pilas

Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.

Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:

   vacia    :: Pila a
   apila    :: a -> Pila a -> Pila a
   cima     :: Pila a -> a
   desapila :: Pila a -> Pila a
   esVacia  :: Pila a -> Bool

vacia :: Pila a

apila :: a -> Pila a -> Pila a

cima :: Pila a -> a

desapila :: Pila a -> Pila a

esVacia :: Pila a -> Bool

tales que

vacia es la pila vacía.
(apila x p) es la pila obtenida añadiendo x al principio de p.
(cima p) es la cima de la pila p.
(desapila p) es la pila obtenida suprimiendo la cima de p.
(esVacia p) se verifica si p es la pila vacía.

Las operaciones tienen que verificar las siguientes propiedades:

cima(apila(x, p) == x
desapila(apila(x, p)) == p
esVacia(vacia)
not esVacia(apila(x, p))

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

El TAD de las pilas se encuentra en el módulo Pila.hs cuyo contenido es el siguiente:

module TAD.Pila
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import TAD.PilaConListas
-- import TAD.PilaConSucesiones

module TAD.Pila

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import TAD.PilaConListas

-- import TAD.PilaConSucesiones

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo PilaConListas.hs cuyo contenido es el siguiente:

module TAD.PilaConListas
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import Test.QuickCheck

-- Representación de las pilas mediante listas.
newtype Pila a = P [a]
  deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P [])     = "-"
escribePila (P [x])    = show x
escribePila (P (x:xs)) = show x ++ " | " ++ escribePila (P xs)

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

-- Ejemplo de pila:
--    λ> apila 1 (apila 2 (apila 3 vacia))
--    1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,
--    λ> vacia
--    -
vacia   :: Pila a
vacia = P []

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
--    λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))
--    4 | 3 | 2 | 5
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x:xs)

-- (cima p) es la cima de la pila p. Por ejemplo,
--    λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P [])    = error "cima de la pila vacia"
cima (P (x:_)) = x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
desapila :: Pila a -> Pila a
desapila (P [])     = error "desapila la pila vacia"
desapila (P (_:xs)) = P  xs

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False
--    esVacia vacia                               ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = null xs

-- Generador de pilas                                          --
-- ==================

-- genPila es un generador de pilas. Por ejemplo,
--    λ> sample genPila
--    -
--    0|0|-
--    -
--    -6|4|-3|3|0|-
--    -
--    9|5|-1|-3|0|-8|-5|-7|2|-
--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
--    2|-14|-5|2|-
--    5|9|-
--    -1|-14|5|-
--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: (Arbitrary a, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila

-- Propiedades
-- ===========

-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))

-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

module TAD.PilaConListas

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import Test.QuickCheck

-- Representación de las pilas mediante listas.

newtype Pila a = P [a]

deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por

-- ejemplo,

-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"

escribePila :: Show a => Pila a -> String

escribePila (P []) = "-"

escribePila (P [x]) = show x

escribePila (P (x:xs)) = show x ++ " | " ++ escribePila (P xs)

-- Procedimiento de escritura de pilas.

instance Show a => Show (Pila a) where

show = escribePila

-- Ejemplo de pila:

-- λ> apila 1 (apila 2 (apila 3 vacia))

-- 1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Pila a

vacia = P []

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por

-- ejemplo,

-- λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))

-- 4 | 3 | 2 | 5

apila :: a -> Pila a -> Pila a

apila x (P xs) = P (x:xs)

-- (cima p) es la cima de la pila p. Por ejemplo,

-- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 4

cima :: Pila a -> a

cima (P []) = error "cima de la pila vacia"

cima (P (x:_)) = x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 3 | 2 | 5

desapila :: Pila a -> Pila a

desapila (P []) = error "desapila la pila vacia"

desapila (P (_:xs)) = P xs

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,

-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Pila a -> Bool

esVacia (P xs) = null xs

-- Generador de pilas --

-- ==================

-- genPila es un generador de pilas. Por ejemplo,

-- λ> sample genPila

-- -

-- 0|0|-

-- -

-- -6|4|-3|3|0|-

-- -

-- 9|5|-1|-3|0|-8|-5|-7|2|-

-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-

-- 2|-14|-5|2|-

-- 5|9|-

-- -1|-14|5|-

-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-

genPila :: (Arbitrary a, Num a) => Gen (Pila a)

genPila = do

xs <- listOf arbitrary

return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where

arbitrary = genPila

-- Propiedades

-- ===========

-- Las propiedades son

prop_pilas :: Int -> Pila Int -> Bool

prop_pilas x p =

cima (apila x p) == x &&

desapila (apila x p) == p &&

esVacia vacia &&

not (esVacia (apila x p))

-- La comprobación e:

-- λ> quickCheck prop_pilas

-- +++ OK, passed 100 tests.

2.3. Implementación de las pilas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo PilaConSucesiones.hs cuyo contenido es el siguiente:

module TAD.PilaConSucesiones
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import Data.Sequence as S
import Test.QuickCheck

-- Representación de las pilas mediante sucesiones.
newtype Pila a = P (Seq a)
  deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P xs) = case viewl xs of
    EmptyL   -> "-"
    x :< xs' -> case viewl xs' of
        EmptyL -> show x
        _      -> show x ++ " | " ++ escribePila (P xs')

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

-- Ejemplo de pila:
--    λ> apila 1 (apila 2 (apila 3 vacia))
--    1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,
--    λ> vacia
--    -
vacia   :: Pila a
vacia = P empty

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
--    λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))
--    5 | 2 | 3 | 4
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x <| xs)

-- (cima p) es la cima de la pila p. Por ejemplo,
--    λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P xs) = case viewl xs of
  EmptyL -> error "cima de la pila vacia"
  x :< _ -> x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
desapila :: Pila a -> Pila a
desapila (P xs) = case viewl xs of
  EmptyL   -> error "desapila la pila vacia"
  _ :< xs' -> P xs'

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False
--    esVacia vacia                               ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = S.null xs

-- Generador de pilas                                          --
-- ==================

-- genPila es un generador de pilas. Por ejemplo,
--    λ> sample genPila
--    -
--    0|0|-
--    -
--    -6|4|-3|3|0|-
--    -
--    9|5|-1|-3|0|-8|-5|-7|2|-
--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
--    2|-14|-5|2|-
--    5|9|-
--    -1|-14|5|-
--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: (Arbitrary a, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila

-- Propiedades
-- ===========

-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))

-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

module TAD.PilaConSucesiones

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import Data.Sequence as S

import Test.QuickCheck

-- Representación de las pilas mediante sucesiones.

newtype Pila a = P (Seq a)

deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por

-- ejemplo,

-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"

escribePila :: Show a => Pila a -> String

escribePila (P xs) = case viewl xs of

EmptyL -> "-"

x :< xs' -> case viewl xs' of

EmptyL -> show x

_ -> show x ++ " | " ++ escribePila (P xs')

-- Procedimiento de escritura de pilas.

instance Show a => Show (Pila a) where

show = escribePila

-- Ejemplo de pila:

-- λ> apila 1 (apila 2 (apila 3 vacia))

-- 1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Pila a

vacia = P empty

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por

-- ejemplo,

-- λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))

-- 5 | 2 | 3 | 4

apila :: a -> Pila a -> Pila a

apila x (P xs) = P (x <| xs)

-- (cima p) es la cima de la pila p. Por ejemplo,

-- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 4

cima :: Pila a -> a

cima (P xs) = case viewl xs of

EmptyL -> error "cima de la pila vacia"

x :< _ -> x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 3 | 2 | 5

desapila :: Pila a -> Pila a

desapila (P xs) = case viewl xs of

EmptyL -> error "desapila la pila vacia"

_ :< xs' -> P xs'

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,

-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Pila a -> Bool

esVacia (P xs) = S.null xs

-- Generador de pilas --

-- ==================

-- genPila es un generador de pilas. Por ejemplo,

-- λ> sample genPila

-- -

-- 0|0|-

-- -

-- -6|4|-3|3|0|-

-- -

-- 9|5|-1|-3|0|-8|-5|-7|2|-

-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-

-- 2|-14|-5|2|-

-- 5|9|-

-- -1|-14|5|-

-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-

genPila :: (Arbitrary a, Num a) => Gen (Pila a)

genPila = do

xs <- listOf arbitrary

return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where

arbitrary = genPila

-- Propiedades

-- ===========

-- Las propiedades son

prop_pilas :: Int -> Pila Int -> Bool

prop_pilas x p =

cima (apila x p) == x &&

desapila (apila x p) == p &&

esVacia vacia &&

not (esVacia (apila x p))

-- La comprobación e:

-- λ> quickCheck prop_pilas

-- +++ OK, passed 100 tests.

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

La implementación se encuentra en el módulo pila.py cuyo contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]
from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,
                                   desapila, pilaAleatoria)
# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,
#                                   desapila, pilaAleatoria)

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,

desapila, pilaAleatoria)

# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,

# desapila, pilaAleatoria)

3.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo pilaConListas.py en el que se define la clase Pila con los siguientes métodos:

apila(x) añade x al principio de la pila.
cima() devuelve la cima de la pila.
desapila() elimina la cima de la pila.
esVacia() se verifica si la pila es vacía.

Por ejemplo,

   >>> p = Pila()
   >>> p
   -
   >>> p.apila(5)
   >>> p.apila(2)
   >>> p.apila(3)
   >>> p.apila(4)
   >>> p
   4 | 3 | 2 | 5
   >>> p.cima()
   4
   >>> p.desapila()
   >>> p
   3 | 2 | 5
   >>> p.esVacia()
   False
   >>> p = Pila()
   >>> p.esVacia()
   True

>>> p = Pila()

>>> p

>>> p.apila(5)

>>> p.apila(2)

>>> p.apila(3)

>>> p.apila(4)

>>> p

4 | 3 | 2 | 5

>>> p.cima()

>>> p.desapila()

>>> p

3 | 2 | 5

>>> p.esVacia()

False

>>> p = Pila()

>>> p.esVacia()

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> apila(4, apila(3, apila(2, apila(5, vacia()))))
   4 | 3 | 2 | 5
   >>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))
   4
   >>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))
   3 | 2 | 5
   >>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

>>> vacia()

>>> apila(4, apila(3, apila(2, apila(5, vacia()))))

4 | 3 | 2 | 5

>>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))

>>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))

3 | 2 | 5

>>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))

False

>>> esVacia(vacia())

True

Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificación.

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]

from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante Listas
# ==================================

@dataclass
class Pila(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return " | ".join(str(x) for x in self._elementos)

    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.insert(0, x)

    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.

        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return not self._elementos

    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]

    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.pop(0)

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    aux = deepcopy(p)
    aux.apila(x)
    return aux

def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    aux = deepcopy(p)
    aux.desapila()
    return aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    return st.lists(st.integers()).map(Pila)

# Comprobación de las propiedades de las pilas
# ============================================

# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))

# La comprobación es
#    > poetry run pytest -q pilaConListas.py
#    1 passed in 0.25s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante Listas

# ==================================

@dataclass

class Pila(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la pila separados por " | ".

Si la pila está vacía, devuelve "-".

"""

if len(self._elementos) == 0:

return '-'

return " | ".join(str(x) for x in self._elementos)

def apila(self, x: A) -> None:

"""

Agrega el elemento x al inicio de la pila.

"""

self._elementos.insert(0, x)

def esVacia(self) -> bool:

"""

Verifica si la pila está vacía.

Devuelve True si la pila está vacía, False en caso contrario.

"""

return not self._elementos

def cima(self) -> A:

"""

Devuelve el elemento en la cima de la pila.

"""

return self._elementos[0]

def desapila(self) -> None:

"""

Elimina el elemento en la cima de la pila.

"""

self._elementos.pop(0)

# Funciones del tipo de las listas

# ================================

def vacia() -> Pila[A]:

"""

Crea y devuelve una pila vacía de tipo A.

"""

p: Pila[A] = Pila()

return p

def apila(x: A, p: Pila[A]) -> Pila[A]:

"""

Añade un elemento x al tope de la pila p y devuelve una copia de la

pila modificada.

"""

aux = deepcopy(p)

aux.apila(x)

return aux

def esVacia(p: Pila[A]) -> bool:

"""

Devuelve True si la pila está vacía, False si no lo está.

"""

return p.esVacia()

def cima(p: Pila[A]) -> A:

"""

Devuelve el elemento en la cima de la pila p.

"""

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

"""

Elimina el elemento en la cima de la pilla p y devuelve una copia de la

pila resultante.

"""

aux = deepcopy(p)

aux.desapila()

return aux

# Generador de pilas

# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

"""

Genera una estrategia de búsqueda para generar pilas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase pila.

"""

return st.lists(st.integers()).map(Pila)

# Comprobación de las propiedades de las pilas

# ============================================

# Las propiedades son

@given(p=pilaAleatoria(), x=st.integers())

def test_pila(p: Pila[int], x: int) -> None:

assert cima(apila(x, p)) == x

assert desapila(apila(x, p)) == p

assert esVacia(vacia())

assert not esVacia(apila(x, p))

# La comprobación es

# > poetry run pytest -q pilaConListas.py

# 1 passed in 0.25s

3.3. Implementación de las pilas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo pilaConDeque.py y su contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]

from collections import deque
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas
# ==================================

@dataclass
class Pila(Generic[A]):
    _elementos: deque[A] = field(default_factory=deque)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)

    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.appendleft(x)

    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.

        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return len(self._elementos) == 0

    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]

    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.popleft()

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    _aux = deepcopy(p)
    _aux.apila(x)
    return _aux

def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    _aux = deepcopy(p)
    _aux.desapila()
    return _aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    def _creaPila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        pila._elementos.extendleft(elementos)
        return pila
    return st.builds(_creaPila, st.lists(st.integers()))

# Comprobación de las propiedades de las pilas
# ============================================

# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))

# La comprobación es
#    > poetry run pytest -q pilaConQueue.py
#    1 passed in 0.25s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from collections import deque

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas

# ==================================

@dataclass

class Pila(Generic[A]):

_elementos: deque[A] = field(default_factory=deque)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la pila separados por " | ".

Si la pila está vacía, devuelve "-".

"""

if len(self._elementos) == 0:

return '-'

return ' | '.join(str(x) for x in self._elementos)

def apila(self, x: A) -> None:

"""

Agrega el elemento x al inicio de la pila.

"""

self._elementos.appendleft(x)

def esVacia(self) -> bool:

"""

Verifica si la pila está vacía.

Devuelve True si la pila está vacía, False en caso contrario.

"""

return len(self._elementos) == 0

def cima(self) -> A:

"""

Devuelve el elemento en la cima de la pila.

"""

return self._elementos[0]

def desapila(self) -> None:

"""

Elimina el elemento en la cima de la pila.

"""

self._elementos.popleft()

# Funciones del tipo de las listas

# ================================

def vacia() -> Pila[A]:

"""

Crea y devuelve una pila vacía de tipo A.

"""

p: Pila[A] = Pila()

return p

def apila(x: A, p: Pila[A]) -> Pila[A]:

"""

Añade un elemento x al tope de la pila p y devuelve una copia de la

pila modificada.

"""

_aux = deepcopy(p)

_aux.apila(x)

return _aux

def esVacia(p: Pila[A]) -> bool:

"""

Devuelve True si la pila está vacía, False si no lo está.

"""

return p.esVacia()

def cima(p: Pila[A]) -> A:

"""

Devuelve el elemento en la cima de la pila p.

"""

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

"""

Elimina el elemento en la cima de la pilla p y devuelve una copia de la

pila resultante.

"""

_aux = deepcopy(p)

_aux.desapila()

return _aux

# Generador de pilas

# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

"""

Genera una estrategia de búsqueda para generar pilas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase pila.

"""

def _creaPila(elementos: list[int]) -> Pila[int]:

pila: Pila[int] = vacia()

pila._elementos.extendleft(elementos)

return pila

return st.builds(_creaPila, st.lists(st.integers()))

# Comprobación de las propiedades de las pilas

# ============================================

# Las propiedades son

@given(p=pilaAleatoria(), x=st.integers())

def test_pila(p: Pila[int], x: int) -> None:

assert cima(apila(x, p)) == x

assert desapila(apila(x, p)) == p

assert esVacia(vacia())

assert not esVacia(apila(x, p))

# La comprobación es

# > poetry run pytest -q pilaConQueue.py

# 1 passed in 0.25s

Valor de una expresión vectorial

PorJosé A. Alonso 19-enero-20231-enero-2023

Se consideran las expresiones vectoriales formadas por un vector, la suma de dos expresiones vectoriales o el producto de un entero por una expresión vectorial. El siguiente tipo de dato define las expresiones vectoriales

   data ExpV = Vec Int Int
             | Sum ExpV ExpV
             | Mul Int ExpV
     deriving Show

data ExpV = Vec Int Int

| Sum ExpV ExpV

| Mul Int ExpV

deriving Show

Definir la función

   valorEV :: ExpV -> (Int,Int)

1	valorEV :: ExpV -> (Int,Int)

tal que valorEV e es el valorEV de la expresión vectorial e. Por ejemplo,

   valorEV (Vec 1 2)                                  ==  (1,2)
   valorEV (Sum (Vec 1 2) (Vec 3 4))                  ==  (4,6)
   valorEV (Mul 2 (Vec 3 4))                          ==  (6,8)
   valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)
   valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)

valorEV (Vec 1 2) == (1,2)

valorEV (Sum (Vec 1 2) (Vec 3 4)) == (4,6)

valorEV (Mul 2 (Vec 3 4)) == (6,8)

valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4))) == (8,12)

valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4))) == (8,12)

Soluciones

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

Soluciones en Haskell

data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
  deriving Show

-- 1ª solución
-- ===========

valorEV1 :: ExpV -> (Int,Int)
valorEV1 (Vec x y)   = (x,y)
valorEV1 (Sum e1 e2) = (x1+x2,y1+y2)
  where (x1,y1) = valorEV1 e1
        (x2,y2) = valorEV1 e2
valorEV1 (Mul n e)   = (n*x,n*y)
  where (x,y) = valorEV1 e

-- 2ª solución
-- ===========

valorEV2 :: ExpV -> (Int,Int)
valorEV2 (Vec a b)   = (a, b)
valorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)
valorEV2 (Mul n e1)  = multiplica n (valorEV2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)

data ExpV = Vec Int Int

| Sum ExpV ExpV

| Mul Int ExpV

deriving Show

-- 1ª solución

-- ===========

valorEV1 :: ExpV -> (Int,Int)

valorEV1 (Vec x y) = (x,y)

valorEV1 (Sum e1 e2) = (x1+x2,y1+y2)

where (x1,y1) = valorEV1 e1

(x2,y2) = valorEV1 e2

valorEV1 (Mul n e) = (n*x,n*y)

where (x,y) = valorEV1 e

-- 2ª solución

-- ===========

valorEV2 :: ExpV -> (Int,Int)

valorEV2 (Vec a b) = (a, b)

valorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)

valorEV2 (Mul n e1) = multiplica n (valorEV2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)

suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)

multiplica n (a,b) = (n*a,n*b)

Soluciones en Python

from dataclasses import dataclass


@dataclass
class ExpV:
    pass

@dataclass
class Vec(ExpV):
    x: int
    y: int

@dataclass
class Sum(ExpV):
    x: ExpV
    y: ExpV

@dataclass
class Mul(ExpV):
    x: int
    y: ExpV

# 1ª solución
# ===========

def valorEV1(e: ExpV) -> tuple[int, int]:
    match e:
        case Vec(x, y):
            return (x, y)
        case Sum(e1, e2):
            x1, y1 = valorEV1(e1)
            x2, y2 = valorEV1(e2)
            return (x1 + x2, y1 + y2)
        case Mul(n, e):
            x, y = valorEV1(e)
            return (n * x, n * y)
    assert False

# 2ª solución
# ===========

def suma(p: tuple[int, int], q: tuple[int, int]) -> tuple[int, int]:
    a, b = p
    c, d = q
    return (a + c, b + d)

def multiplica(n: int, p: tuple[int, int]) -> tuple[int, int]:
    a, b = p
    return (n * a, n * b)

def valorEV2(e: ExpV) -> tuple[int, int]:
    match e:
        case Vec(x, y):
            return (x, y)
        case Sum(e1, e2):
            return suma(valorEV2(e1), valorEV2(e2))
        case Mul(n, e):
            return multiplica(n, valorEV2(e))
    assert False

from dataclasses import dataclass

@dataclass

class ExpV:

pass

@dataclass

class Vec(ExpV):

x: int

y: int

@dataclass

class Sum(ExpV):

x: ExpV

y: ExpV

@dataclass

class Mul(ExpV):

x: int

y: ExpV

# 1ª solución

# ===========

def valorEV1(e: ExpV) -> tuple[int, int]:

match e:

case Vec(x, y):

return (x, y)

case Sum(e1, e2):

x1, y1 = valorEV1(e1)

x2, y2 = valorEV1(e2)

return (x1 + x2, y1 + y2)

case Mul(n, e):

x, y = valorEV1(e)

return (n * x, n * y)

assert False

# 2ª solución

# ===========

def suma(p: tuple[int, int], q: tuple[int, int]) -> tuple[int, int]:

a, b = p

c, d = q

return (a + c, b + d)

def multiplica(n: int, p: tuple[int, int]) -> tuple[int, int]:

a, b = p

return (n * a, n * b)

def valorEV2(e: ExpV) -> tuple[int, int]:

match e:

case Vec(x, y):

return (x, y)

case Sum(e1, e2):

return suma(valorEV2(e1), valorEV2(e2))

case Mul(n, e):

return multiplica(n, valorEV2(e))

assert False

Valor de expresiones aritméticas generales

PorJosé A. Alonso 18-enero-202331-diciembre-2022

Las operaciones de suma, resta y multiplicación se pueden representar mediante el siguiente tipo de datos

   data Op = S | R | M

1	data Op = S \| R \| M

La expresiones aritméticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico

   data Expr = C Int
             | A Op Expr Expr

1 2	data Expr = C Int \| A Op Expr Expr

Por ejemplo, la expresión

   (7-3)+(2*5)

1	(7-3)+(2*5)

se representa por

   A S (A R (C 7) (C 3)) (A M (C 2) (C 5))

1	A S (A R (C 7) (C 3)) (A M (C 2) (C 5))

Definir la función

   valor :: Expr -> Int

1	valor :: Expr -> Int

tal que valor e es el valor de la expresión e. Por ejemplo,

   valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5)))  ==  14
   valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5)))  ==  28

1 2	valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5))) == 14 valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5))) == 28

Soluciones

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

Soluciones en Haskell

data Op = S | R | M

data Expr = C Int
          | A Op Expr Expr

-- 1ª solución
-- ===========

valor :: Expr -> Int
valor (C x)      = x
valor (A o e1 e2) = aplica o (valor e1) (valor e2)
  where aplica :: Op -> Int -> Int -> Int
        aplica S x y = x+y
        aplica R x y = x-y
        aplica M x y = x*y

-- 2ª solución
-- ===========

valor2 :: Expr -> Int
valor2 (C n)    = n
valor2 (A o x y) = sig o (valor2 x) (valor2 y)
  where sig :: Op -> Int -> Int -> Int
        sig S = (+)
        sig M = (*)
        sig R = (-)

data Op = S | R | M

data Expr = C Int

| A Op Expr Expr

-- 1ª solución

-- ===========

valor :: Expr -> Int

valor (C x) = x

valor (A o e1 e2) = aplica o (valor e1) (valor e2)

where aplica :: Op -> Int -> Int -> Int

aplica S x y = x+y

aplica R x y = x-y

aplica M x y = x*y

-- 2ª solución

-- ===========

valor2 :: Expr -> Int

valor2 (C n) = n

valor2 (A o x y) = sig o (valor2 x) (valor2 y)

where sig :: Op -> Int -> Int -> Int

sig S = (+)

sig M = (*)

sig R = (-)

Soluciones en Python

from dataclasses import dataclass
from enum import Enum

Op = Enum('Op', ['S', 'R', 'M'])

@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class A(Expr):
    o: Op
    x: Expr
    y: Expr

def aplica(o: Op, x: int, y: int) -> int:
    match o:
        case Op.S:
            return x + y
        case Op.R:
            return x - y
        case Op.M:
            return x * y
    assert False

def valor(e: Expr) -> int:
    match e:
        case C(x):
            return x
        case A(o, e1, e2):
            return aplica(o, valor(e1), valor(e2))
    assert False

from dataclasses import dataclass

from enum import Enum

Op = Enum('Op', ['S', 'R', 'M'])

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class A(Expr):

o: Op

x: Expr

y: Expr

def aplica(o: Op, x: int, y: int) -> int:

match o:

case Op.S:

return x + y

case Op.R:

return x - y

case Op.M:

return x * y

assert False

def valor(e: Expr) -> int:

match e:

case C(x):

return x

case A(o, e1, e2):

return aplica(o, valor(e1), valor(e2))

assert False

Máximos valores de una expresión aritmética

PorJosé A. Alonso 17-enero-202331-diciembre-2022

Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos

   data Expr = C Int
             | X
             | S Expr Expr
             | R Expr Expr
             | P Expr Expr
             | E Expr Int
     deriving (Eq, Show)

data Expr = C Int

| X

| S Expr Expr

| R Expr Expr

| P Expr Expr

| E Expr Int

deriving (Eq, Show)

Por ejemplo, la expresión

   3*x - (x+2)^7

1	3*x - (x+2)^7

se puede definir por

   R (P (C 3) X) (E (S X (C 2)) 7)

1	R (P (C 3) X) (E (S X (C 2)) 7)

Definir la función

   maximo :: Expr -> [Int] -> (Int,[Int])

1	maximo :: Expr -> [Int] -> (Int,[Int])

tal que maximo e xs es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

   λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3]
   (100,[0,1])

1 2	λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3] (100,[0,1])

Soluciones

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

Soluciones en Haskell

data Expr = C Int
          | X
          | S Expr Expr
          | R Expr Expr
          | P Expr Expr
          | E Expr Int
  deriving (Eq, Show)

maximo :: Expr -> [Int] -> (Int,[Int])
maximo e ns = (m,[n | n <- ns, valor e n == m])
  where m = maximum [valor e n | n <- ns]

valor :: Expr -> Int -> Int
valor (C x) _     = x
valor X     n     = n
valor (S e1 e2) n = valor e1 n + valor e2 n
valor (R e1 e2) n = valor e1 n - valor e2 n
valor (P e1 e2) n = valor e1 n * valor e2 n
valor (E e1 m1) n = valor e1 n ^ m1

data Expr = C Int

| X

| S Expr Expr

| R Expr Expr

| P Expr Expr

| E Expr Int

deriving (Eq, Show)

maximo :: Expr -> [Int] -> (Int,[Int])

maximo e ns = (m,[n | n <- ns, valor e n == m])

where m = maximum [valor e n | n <- ns]

valor :: Expr -> Int -> Int

valor (C x) _ = x

valor X n = n

valor (S e1 e2) n = valor e1 n + valor e2 n

valor (R e1 e2) n = valor e1 n - valor e2 n

valor (P e1 e2) n = valor e1 n * valor e2 n

valor (E e1 m1) n = valor e1 n ^ m1

Soluciones en Python

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class X(Expr):
    pass

@dataclass
class S(Expr):
    x: Expr
    y: Expr

@dataclass
class R(Expr):
    x: Expr
    y: Expr

@dataclass
class P(Expr):
    x: Expr
    y: Expr

@dataclass
class E(Expr):
    x: Expr
    y: int

def valor(e: Expr, n: int) -> int:
    match e:
        case C(a):
            return a
        case X():
            return n
        case S(e1, e2):
            return valor(e1, n) + valor(e2, n)
        case R(e1, e2):
            return valor(e1, n) - valor(e2, n)
        case P(e1, e2):
            return valor(e1, n) * valor(e2, n)
        case E(e1, m):
            return valor(e1, n) ** m
    assert False

def maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]:
    m = max((valor(e, n) for n in ns))
    return (m, [n for n in ns if valor(e, n) == m])

from dataclasses import dataclass

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class X(Expr):

pass

@dataclass

class S(Expr):

x: Expr

y: Expr

@dataclass

class R(Expr):

x: Expr

y: Expr

@dataclass

class P(Expr):

x: Expr

y: Expr

@dataclass

class E(Expr):

x: Expr

y: int

def valor(e: Expr, n: int) -> int:

match e:

case C(a):

return a

case X():

return n

case S(e1, e2):

return valor(e1, n) + valor(e2, n)

case R(e1, e2):

return valor(e1, n) - valor(e2, n)

case P(e1, e2):

return valor(e1, n) * valor(e2, n)

case E(e1, m):

return valor(e1, n) ** m

assert False

def maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]:

m = max((valor(e, n) for n in ns))

return (m, [n for n in ns if valor(e, n) == m])

Expresiones aritméticas reducibles

PorJosé A. Alonso 16-enero-202330-diciembre-2022

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

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

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

Definir la función

   reducible :: Expr -> Bool

1	reducible :: Expr -> Bool

tal que reducible a se verifica si a es una expresión reducible; es decir, contiene una operación en la que los dos operandos son números. Por ejemplo,

   reducible (S (C 3) (C 4))             == True
   reducible (S (C 3) (V 'x'))           == False
   reducible (S (C 3) (P (C 4) (C 5)))   == True
   reducible (S (V 'x') (P (C 4) (C 5))) == True
   reducible (S (C 3) (P (V 'x') (C 5))) == False
   reducible (C 3)                       == False
   reducible (V 'x')                     == False

reducible (S (C 3) (C 4)) == True

reducible (S (C 3) (V 'x')) == False

reducible (S (C 3) (P (C 4) (C 5))) == True

reducible (S (V 'x') (P (C 4) (C 5))) == True

reducible (S (C 3) (P (V 'x') (C 5))) == False

reducible (C 3) == False

reducible (V 'x') == False

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

reducible :: Expr -> Bool
reducible (C _)           = False
reducible (V _)           = False
reducible (S (C _) (C _)) = True
reducible (S a b)         = reducible a || reducible b
reducible (P (C _) (C _)) = True
reducible (P a b)         = reducible a || reducible b

data Expr = C Int

| V Char

| S Expr Expr

| P Expr Expr

reducible :: Expr -> Bool

reducible (C _) = False

reducible (V _) = False

reducible (S (C _) (C _)) = True

reducible (S a b) = reducible a || reducible b

reducible (P (C _) (C _)) = True

reducible (P a b) = reducible a || reducible b

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 reducible(e: Expr) -> bool:
    match e:
        case C(_):
            return False
        case V(_):
            return False
        case S(C(_), C(_)):
            return True
        case S(a, b):
            return reducible(a) or reducible(b)
        case P(C(_), C(_)):
            return True
        case P(a, b):
            return reducible(a) or reducible(b)
    assert False

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 reducible(e: Expr) -> bool:

match e:

case C(_):

return False

case V(_):

return False

case S(C(_), C(_)):

return True

case S(a, b):

return reducible(a) or reducible(b)

case P(C(_), C(_)):

return True

case P(a, b):

return reducible(a) or reducible(b)

assert False

Sustitución en una expresión aritmética

PorJosé A. Alonso 13-enero-202330-diciembre-2022

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)

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

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

Definir la función

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

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,

   λ> 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'))

λ> 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)

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

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

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

PorJosé A. Alonso 12-enero-202330-diciembre-2022

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

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

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

Definir la función

   sumas :: Expr -> Int

1	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

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

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

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

Valor de una expresión aritmética con variables

PorJosé A. Alonso 11-enero-202330-diciembre-2022

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

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

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

Definir la función

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

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,

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

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.

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

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

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

El tipo de las expresiones aritméticas con variables

PorJosé A. Alonso 11-enero-202326-abril-2023

1. El tipo de las expresiones aritméticas con variables en Haskell

La expresión 2*(a+5) puede representarse por

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

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

usando el tipo de las expresiones aritméticas con variables definido como se muestra a continuación.

module Expresion_aritmetica_con_variables where

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

module Expresion_aritmetica_con_variables where

data Expr = C Int

| V Char

| S Expr Expr

| P Expr Expr

deriving (Eq, Show)

2. El tipo de las expresiones aritméticas con variables en Python

La expresión 2*(a+5) puede representarse por

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

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

usando el tipo de las expresiones aritméticas con variables definido como se muestra a continuación.

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

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

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

PorJosé A. Alonso 10-enero-202330-diciembre-2022

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

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)

1	P X (S (C 13) X)

Definir la función

   numVars :: Expr -> Int

1	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

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

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

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

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

PorJosé A. Alonso 9-enero-202330-diciembre-2022

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

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)

1	P X (S (C 13) X)

Definir la función

   valor :: Expr -> Int -> Int

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,

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

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.

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

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

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

Tipo de expresiones aritméticas con una variable

PorJosé A. Alonso 9-enero-202320-abril-2023

1. El tipo de las expresiones aritméticas con una variable en Haskell

La expresión X·(13+X) se representa por

   P(X(), S(C(13), X()))

1	P(X(), S(C(13), X()))

usando el tipo de las expresiones aritméticas con una variable (denotada por X) que se define como se muestra a continuación,

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

data Expr = C Int

| V Char

| S Expr Expr

| P Expr Expr

2. El tipo de las expresiones aritméticas con una variable en Python

La expresión X*(13+X) se representa por

   P(X(), S(C(13), X()))

1	P(X(), S(C(13), X()))

usando el tipo de las expresiones aritméticas con una variable (denotada por X) que se define como se muestra a continuación,

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

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

Aplicación de una función a una expresión aritmética

PorJosé A. Alonso 6-enero-202316-abril-2023

Usando el tipo de las expresiones aritméticas básicas, definir la función

   aplica :: (Int -> Int) -> Expr -> Expr

1	aplica :: (Int -> Int) -> Expr -> Expr

tal que aplica f e es la expresión obtenida aplicando la función f a cada uno de los números de la expresión e. Por ejemplo,

   λ> aplica (+2) (S (P (C 3) (C 5)) (P (C 6) (C 7)))
   S (P (C 5) (C 7)) (P (C 8) (C 9))
   λ> aplica (*2) (S (P (C 3) (C 5)) (P (C 6) (C 7)))
   S (P (C 6) (C 10)) (P (C 12) (C 14))

λ> aplica (+2) (S (P (C 3) (C 5)) (P (C 6) (C 7)))

S (P (C 5) (C 7)) (P (C 8) (C 9))

λ> aplica (*2) (S (P (C 3) (C 5)) (P (C 6) (C 7)))

S (P (C 6) (C 10)) (P (C 12) (C 14))

Soluciones

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

Soluciones en Haskell

import Expresion_aritmetica_basica (Expr(..))

aplica :: (Int -> Int) -> Expr -> Expr
aplica f (C x)     = C (f x)
aplica f (S e1 e2) = S (aplica f e1) (aplica f e2)
aplica f (P e1 e2) = P (aplica f e1) (aplica f e2)

import Expresion_aritmetica_basica (Expr(..))

aplica :: (Int -> Int) -> Expr -> Expr

aplica f (C x) = C (f x)

aplica f (S e1 e2) = S (aplica f e1) (aplica f e2)

aplica f (P e1 e2) = P (aplica f e1) (aplica f e2)

Soluciones en Python

from typing import Callable
from src.expresion_aritmetica_basica import Expr, C, S, P

def aplica(f: Callable[[int], int], e: Expr) -> Expr:
    match e:
        case C(x):
            return C(f(x))
        case S(x, y):
            return S(aplica(f, x), aplica(f, y))
        case P(x, y):
            return P(aplica(f, x), aplica(f, y))
    assert False

from typing import Callable

from src.expresion_aritmetica_basica import Expr, C, S, P

def aplica(f: Callable[[int], int], e: Expr) -> Expr:

match e:

case C(x):

return C(f(x))

case S(x, y):

return S(aplica(f, x), aplica(f, y))

case P(x, y):

return P(aplica(f, x), aplica(f, y))

assert False

Valor de una expresión aritmética básica

PorJosé A. Alonso 5-enero-202316-abril-2023

Usando el tipo de las expresiones aritméticas básicas, definir la función

   valor :: Expr -> Int

1	valor :: Expr -> Int

tal que valor e es el valor de la expresión aritmética e. Por ejemplo,

   valor (P (C 2) (S (C 3) (C 7)))  ==  20

1	valor (P (C 2) (S (C 3) (C 7))) == 20

Soluciones

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

Soluciones en Haskell

import Expresion_aritmetica_basica (Expr(..))

valor :: Expr -> Int
valor (C x)   = x
valor (S x y) = valor x + valor y
valor (P x y) = valor x * valor y

import Expresion_aritmetica_basica (Expr(..))

valor :: Expr -> Int

valor (C x) = x

valor (S x y) = valor x + valor y

valor (P x y) = valor x * valor y

Soluciones en Python

from src.expresion_aritmetica_basica import Expr, C, S, P

def valor(e: Expr) -> int:
    match e:
        case C(x):
            return x
        case S(x, y):
            return valor(x) + valor(y)
        case P(x, y):
            return valor(x) * valor(y)
    assert False

from src.expresion_aritmetica_basica import Expr, C, S, P

def valor(e: Expr) -> int:

match e:

case C(x):

return x

case S(x, y):

return valor(x) + valor(y)

case P(x, y):

return valor(x) * valor(y)

assert False

El tipo de las expresiones aritméticas básicas

PorJosé A. Alonso 5-enero-202316-abril-2023

1. El tipo de las expresiones aritméticas básicas en Haskell

La expresión aritmética 2*(3+7) se representa por

   P (C 2) (S (C 3) (C 7))

1	P (C 2) (S (C 3) (C 7))

usando el tipo de dato definido a continuación.

module Expresion_aritmetica_basica where

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

module Expresion_aritmetica_basica where

data Expr = C Int

| S Expr Expr

| P Expr Expr

2. El tipo de las expresiones aritméticas básicas en Python

La expresión aritmética 2*(3+7) se representa por

   P(C(2), S(C(3), C(7)))

1	P(C(2), S(C(3), C(7)))

usando el tipo de dato definido a continuación.

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class S(Expr):
    x: Expr
    y: Expr

@dataclass
class P(Expr):
    x: Expr
    y: Expr

from dataclasses import dataclass

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class S(Expr):

x: Expr

y: Expr

@dataclass

class P(Expr):

x: Expr

y: Expr

Valor de un árbol booleano

PorJosé A. Alonso 4-enero-202329-diciembre-2022

Se consideran los árboles con operaciones booleanas definidos por

   data Arbol = H Bool
              | Conj Arbol Arbol
              | Disy Arbol Arbol
              | Neg Arbol

data Arbol = H Bool

| Conj Arbol Arbol

| Disy Arbol Arbol

| Neg Arbol

Por ejemplo, los árboles

               Conj                            Conj
              /   \                           /   \
             /     \                         /     \
          Disy      Conj                  Disy      Conj
         /   \       /  \                /   \      /   \
      Conj    Neg   Neg True          Conj    Neg   Neg  True
      /  \    |     |                 /  \    |     |
   True False False False          True False True  False

Conj Conj

/ \ / \

Disy Conj Disy Conj

/ \ / \ / \ / \

Conj Neg Neg True Conj Neg Neg True

/ \ | | / \ | |

True False False False True False True False

se definen por

   ej1, ej2:: Arbol
   ej1 = Conj (Disy (Conj (H True) (H False))
                    (Neg (H False)))
              (Conj (Neg (H False))
                    (H True))

   ej2 = Conj (Disy (Conj (H True) (H False))
                    (Neg (H True)))
              (Conj (Neg (H False))
                    (H True))

ej1, ej2:: Arbol

ej1 = Conj (Disy (Conj (H True) (H False))

(Neg (H False)))

(Conj (Neg (H False))

(H True))

ej2 = Conj (Disy (Conj (H True) (H False))

(Neg (H True)))

(Conj (Neg (H False))

(H True))

Definir la función

   valor :: Arbol -> Bool

1	valor :: Arbol -> Bool

tal que valor a) es el resultado de procesar el árbol a realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,

   valor ej1 == True
   valor ej2 == False

1 2	valor ej1 == True valor ej2 == False

Soluciones

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

Soluciones en Haskell

data Arbol = H Bool
           | Conj Arbol Arbol
           | Disy Arbol Arbol
           | Neg Arbol

ej1, ej2 :: Arbol
ej1 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H False)))
           (Conj (Neg (H False))
                 (H True))

ej2 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H True)))
           (Conj (Neg (H False))
                 (H True))

valor :: Arbol -> Bool
valor (H x)      = x
valor (Neg a)    = not (valor a)
valor (Conj i d) = valor i && valor d
valor (Disy i d) = valor i || valor d

data Arbol = H Bool

| Conj Arbol Arbol

| Disy Arbol Arbol

| Neg Arbol

ej1, ej2 :: Arbol

ej1 = Conj (Disy (Conj (H True) (H False))

(Neg (H False)))

(Conj (Neg (H False))

(H True))

ej2 = Conj (Disy (Conj (H True) (H False))

(Neg (H True)))

(Conj (Neg (H False))

(H True))

valor :: Arbol -> Bool

valor (H x) = x

valor (Neg a) = not (valor a)

valor (Conj i d) = valor i && valor d

valor (Disy i d) = valor i || valor d

Soluciones en Python

from dataclasses import dataclass

@dataclass
class Arbol:
    pass

@dataclass
class H(Arbol):
    x: bool

@dataclass
class Conj(Arbol):
    i: Arbol
    d: Arbol

@dataclass
class Disy(Arbol):
    i: Arbol
    d: Arbol

@dataclass
class Neg(Arbol):
    a: Arbol

ej1: Arbol = Conj(Disy(Conj(H(True), H(False)),
                       (Neg(H(False)))),
                  (Conj(Neg(H(False)),
                        (H(True)))))

ej2: Arbol = Conj(Disy(Conj(H(True), H(False)),
                       (Neg(H(True)))),
                  (Conj(Neg(H(False)),
                        (H(True)))))

def valor(a: Arbol) -> bool:
    match a:
        case H(x):
            return x
        case Neg(b):
            return not valor(b)
        case Conj(i, d):
            return valor(i) and valor(d)
        case Disy(i, d):
            return valor(i) or valor(d)
    assert False

from dataclasses import dataclass

@dataclass

class Arbol:

pass

@dataclass

class H(Arbol):

x: bool

@dataclass

class Conj(Arbol):

i: Arbol

d: Arbol

@dataclass

class Disy(Arbol):

i: Arbol

d: Arbol

@dataclass

class Neg(Arbol):

a: Arbol

ej1: Arbol = Conj(Disy(Conj(H(True), H(False)),

(Neg(H(False)))),

(Conj(Neg(H(False)),

(H(True)))))

ej2: Arbol = Conj(Disy(Conj(H(True), H(False)),

(Neg(H(True)))),

(Conj(Neg(H(False)),

(H(True)))))

def valor(a: Arbol) -> bool:

match a:

case H(x):

return x

case Neg(b):

return not valor(b)

case Conj(i, d):

return valor(i) and valor(d)

case Disy(i, d):

return valor(i) or valor(d)

assert False

Árbol de factorización

PorJosé A. Alonso 3-enero-202328-diciembre-2022

Los divisores medios de un número son los que ocupan la media entre los divisores de n, ordenados de menor a mayor. Por ejemplo, los divisores de 60 son [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] y sus divisores medios son 6 y 10. Para los números que son cuadrados perfectos, sus divisores medios de son sus raíces cuadradas; por ejemplos, los divisores medios de 9 son 3 y 3.

El árbol de factorización de un número compuesto n se construye de la siguiente manera:

la raíz es el número n,
la rama izquierda es el árbol de factorización de su divisor medio menor y
la rama derecha es el árbol de factorización de su divisor medio mayor

Si el número es primo, su árbol de factorización sólo tiene una hoja con dicho número. Por ejemplo, el árbol de factorización de 60 es

       60
      /  \
     6    10
    / \   / \
   2   3 2   5

/ \

6 10

/ \ / \

2 3 2 5

Definir la función

   arbolFactorizacion :: Int -> Arbol

1	arbolFactorizacion :: Int -> Arbol

tal que arbolFactorizacion n es el árbol de factorización de n. Por ejemplo,

   arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5))
   arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3))
   arbolFactorizacion 7  == H 7
   arbolFactorizacion 9  == N 9 (H 3) (H 3)
   arbolFactorizacion 14 == N 14 (H 2) (H 7)
   arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7)
   arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))

arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5))

arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3))

arbolFactorizacion 7 == H 7

arbolFactorizacion 9 == N 9 (H 3) (H 3)

arbolFactorizacion 14 == N 14 (H 2) (H 7)

arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7)

arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

-- 1ª solución
-- ===========

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

arbolFactorizacion1 :: Int -> Arbol
arbolFactorizacion1 n
  | esPrimo n = H n
  | otherwise = N n (arbolFactorizacion1 x) (arbolFactorizacion1 y)
  where (x,y) = divisoresMedio n

-- (esPrimo n) se verifica si n es primo. Por ejemplo,
--    esPrimo 7  ==  True
--    esPrimo 9  ==  False
esPrimo :: Int -> Bool
esPrimo n = divisores n == [1,n]

-- (divisoresMedio n) es el par formado por los divisores medios de
-- n. Por ejemplo,
--    divisoresMedio 30  ==  (5,6)
--    divisoresMedio  7  ==  (1,7)
--    divisoresMedio 16  ==  (4,4)
divisoresMedio :: Int -> (Int,Int)
divisoresMedio n = (n `div` x,x)
  where xs = divisores n
        x  = xs !! (length xs `div` 2)

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución
-- ===========

arbolFactorizacion2 :: Int -> Arbol
arbolFactorizacion2 n
  | x == 1    = H n
  | otherwise = N n (arbolFactorizacion2 x) (arbolFactorizacion2 y)
  where (x,y) = divisoresMedio n

-- (divisoresMedio2 n) es el par formado por los divisores medios de
-- n. Por ejemplo,
--    divisoresMedio2 30  ==  (5,6)
--    divisoresMedio2  7  ==  (1,7)
divisoresMedio2 :: Int -> (Int,Int)
divisoresMedio2 n = (n `div` x,x)
  where m = ceiling (sqrt (fromIntegral n))
        x = head [y | y <- [m..n], n `rem` y == 0]

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_arbolFactorizacion :: Int -> Property
prop_arbolFactorizacion n =
  n > 1 ==> arbolFactorizacion1 n == arbolFactorizacion2 n

-- La comprobación es
--    λ> quickCheck prop_arbolFactorizacion
--    +++ OK, passed 100 tests; 162 discarded.

import Test.QuickCheck

-- 1ª solución

-- ===========

data Arbol = H Int

| N Int Arbol Arbol

deriving (Eq, Show)

arbolFactorizacion1 :: Int -> Arbol

arbolFactorizacion1 n

| esPrimo n = H n

| otherwise = N n (arbolFactorizacion1 x) (arbolFactorizacion1 y)

where (x,y) = divisoresMedio n

-- (esPrimo n) se verifica si n es primo. Por ejemplo,

-- esPrimo 7 == True

-- esPrimo 9 == False

esPrimo :: Int -> Bool

esPrimo n = divisores n == [1,n]

-- (divisoresMedio n) es el par formado por los divisores medios de

-- n. Por ejemplo,

-- divisoresMedio 30 == (5,6)

-- divisoresMedio 7 == (1,7)

-- divisoresMedio 16 == (4,4)

divisoresMedio :: Int -> (Int,Int)

divisoresMedio n = (n `div` x,x)

where xs = divisores n

x = xs !! (length xs `div` 2)

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores :: Int -> [Int]

divisores n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

arbolFactorizacion2 :: Int -> Arbol

arbolFactorizacion2 n

| x == 1 = H n

| otherwise = N n (arbolFactorizacion2 x) (arbolFactorizacion2 y)

where (x,y) = divisoresMedio n

-- (divisoresMedio2 n) es el par formado por los divisores medios de

-- n. Por ejemplo,

-- divisoresMedio2 30 == (5,6)

-- divisoresMedio2 7 == (1,7)

divisoresMedio2 :: Int -> (Int,Int)

divisoresMedio2 n = (n `div` x,x)

where m = ceiling (sqrt (fromIntegral n))

x = head [y | y <- [m..n], n `rem` y == 0]

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_arbolFactorizacion :: Int -> Property

prop_arbolFactorizacion n =

n > 1 ==> arbolFactorizacion1 n == arbolFactorizacion2 n

-- La comprobación es

-- λ> quickCheck prop_arbolFactorizacion

-- +++ OK, passed 100 tests; 162 discarded.

Soluciones en Python

from dataclasses import dataclass
from math import ceil, sqrt

from hypothesis import given
from hypothesis import strategies as st

# 1ª solución
# ===========

@dataclass
class Arbol:
    pass

@dataclass
class H(Arbol):
    x: int

@dataclass
class N(Arbol):
    x: int
    i: Arbol
    d: Arbol

# divisores(n) es la lista de los divisores de n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# divisoresMedio(n) es el par formado por los divisores medios de
# n. Por ejemplo,
#    divisoresMedio(30)  ==  (5,6)
#    divisoresMedio(7)   ==  (1,7)
#    divisoresMedio(16)  ==  (4,4)
def divisoresMedio(n: int) -> tuple[int, int]:
    xs = divisores(n)
    x = xs[len(xs) // 2]
    return (n // x, x)

# esPrimo(n) se verifica si n es primo. Por ejemplo,
#    esPrimo(7)  ==  True
#    esPrimo(9)  ==  False
def esPrimo(n: int) -> bool:
    return divisores(n) == [1, n]

def arbolFactorizacion1(n: int) -> Arbol:
    if esPrimo(n):
        return H(n)
    (x, y) = divisoresMedio(n)
    return N(n, arbolFactorizacion1(x), arbolFactorizacion1(y))

# 2ª solución
# ===========

# divisoresMedio2(n) es el par formado por los divisores medios de
# n. Por ejemplo,
#    divisoresMedio2(30) ==  (5,6)
#    divisoresMedio2(7)  ==  (1,7)
#    divisoresMedio2(16) ==  (4,4)
def divisoresMedio2(n: int) -> tuple[int, int]:
    m = ceil(sqrt(n))
    x = [y for y in range(m, n + 1) if n % y == 0][0]
    return (n // x, x)

def arbolFactorizacion2(n: int) -> Arbol:
    if esPrimo(n):
        return H(n)
    (x, y) = divisoresMedio2(n)
    return N(n, arbolFactorizacion2(x), arbolFactorizacion2(y))

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=2, max_value=200))
def test_arbolFactorizacion(n: int) -> None:
    assert arbolFactorizacion1(n) == arbolFactorizacion2(n)

# La comprobación es
#    src> poetry run pytest -q arbol_de_factorizacion.py
#    1 passed in 0.14s

from dataclasses import dataclass

from math import ceil, sqrt

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

# ===========

@dataclass

class Arbol:

pass

@dataclass

class H(Arbol):

x: int

@dataclass

class N(Arbol):

x: int

i: Arbol

d: Arbol

# divisores(n) es la lista de los divisores de n. Por ejemplo,

# divisores(30) == [1,2,3,5,6,10,15,30]

def divisores(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# divisoresMedio(n) es el par formado por los divisores medios de

# n. Por ejemplo,

# divisoresMedio(30) == (5,6)

# divisoresMedio(7) == (1,7)

# divisoresMedio(16) == (4,4)

def divisoresMedio(n: int) -> tuple[int, int]:

xs = divisores(n)

x = xs[len(xs) // 2]

return (n // x, x)

# esPrimo(n) se verifica si n es primo. Por ejemplo,

# esPrimo(7) == True

# esPrimo(9) == False

def esPrimo(n: int) -> bool:

return divisores(n) == [1, n]

def arbolFactorizacion1(n: int) -> Arbol:

if esPrimo(n):

return H(n)

(x, y) = divisoresMedio(n)

return N(n, arbolFactorizacion1(x), arbolFactorizacion1(y))

# 2ª solución

# ===========

# divisoresMedio2(n) es el par formado por los divisores medios de

# n. Por ejemplo,

# divisoresMedio2(30) == (5,6)

# divisoresMedio2(7) == (1,7)

# divisoresMedio2(16) == (4,4)

def divisoresMedio2(n: int) -> tuple[int, int]:

m = ceil(sqrt(n))

x = [y for y in range(m, n + 1) if n % y == 0][0]

return (n // x, x)

def arbolFactorizacion2(n: int) -> Arbol:

if esPrimo(n):

return H(n)

(x, y) = divisoresMedio2(n)

return N(n, arbolFactorizacion2(x), arbolFactorizacion2(y))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=200))

def test_arbolFactorizacion(n: int) -> None:

assert arbolFactorizacion1(n) == arbolFactorizacion2(n)

# La comprobación es

# src> poetry run pytest -q arbol_de_factorizacion.py

# 1 passed in 0.14s

Elementos del nivel k de un árbol

PorJosé A. Alonso 2-enero-20232-enero-2023

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)

1 2	data Arbol a = H a \| N a (Arbol a) (Arbol a)

Por ejemplo, el árbol

/ \

2 9

/ \

5 4

se representa por

   N 7 (N 2 (H 5) (H 4)) (H 9)

1	N 7 (N 2 (H 5) (H 4)) (H 9)

Un elemento de un árbol se dirá de nivel k si aparece en el árbol a distancia k de la raíz.

Definir la función

   nivel :: Int -> Arbol a -> [a]

1	nivel :: Int -> Arbol a -> [a]

tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,

   nivel 0 (H 5)                          ==  [5]
   nivel 1 (H 5)                          ==  []
   nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [7]
   nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [2,9]
   nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [5,4]
   nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  []

nivel 0 (H 5) == [5]

nivel 1 (H 5) == []

nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [7]

nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [2,9]

nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [5,4]

nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9)) == []

Soluciones

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

Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)

nivel :: Int -> Arbol a -> [a]
nivel 0 (H x)      = [x]
nivel 0 (N x _  _) = [x]
nivel _ (H _ )     = []
nivel k (N _ i d)  = nivel (k-1) i ++ nivel (k-1) d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

nivel :: Int -> Arbol a -> [a]

nivel 0 (H x) = [x]

nivel 0 (N x _ _) = [x]

nivel _ (H _ ) = []

nivel k (N _ i d) = nivel (k-1) i ++ nivel (k-1) d

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def nivel(k: int, a: Arbol[A]) -> list[A]:
    match (k, a):
        case (0, H(x)):
            return [x]
        case (0, N(x, _, _)):
            return [x]
        case (_, H(_)):
            return []
        case (_, N(_, i, d)):
            return nivel(k - 1, i) + nivel(k - 1, d)
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def nivel(k: int, a: Arbol[A]) -> list[A]:

match (k, a):

case (0, H(x)):

return [x]

case (0, N(x, _, _)):

return [x]

case (_, H(_)):

return []

case (_, N(_, i, d)):

return nivel(k - 1, i) + nivel(k - 1, d)

assert False

Existencia de elementos del árbol que verifican una propiedad

PorJosé A. Alonso 30-diciembre-202227-diciembre-2022

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, el árbol

/ \

3 2

/ \

1 4

se representa por

   N 5 (N 3 (H 1) (H 4)) (H 2)

1	N 5 (N 3 (H 1) (H 4)) (H 2)

Definir la función

   algunoArbol :: Arbol t -> (t -> Bool) -> Bool

1	algunoArbol :: Arbol t -> (t -> Bool) -> Bool

tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,

   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True
   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  False

1 2	algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4) == True algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7) == False

Soluciones

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

Soluciones en Haskell

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

algunoArbol :: Arbol a -> (a -> Bool) -> Bool
algunoArbol (H x) p     = p x
algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

algunoArbol :: Arbol a -> (a -> Bool) -> Bool

algunoArbol (H x) p = p x

algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p

Soluciones en Python

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool:
    match a:
        case H(x):
            return p(x)
        case N(x, i, d):
            return p(x) or algunoArbol(i, p) or algunoArbol(d, p)
    assert False

from dataclasses import dataclass

from typing import Callable, Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool:

match a:

case H(x):

return p(x)

case N(x, i, d):

return p(x) or algunoArbol(i, p) or algunoArbol(d, p)

assert False

Árboles con igual estructura

PorJosé A. Alonso 29-diciembre-202226-diciembre-2022

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, los árboles

        5              8             5           5
       / \            / \           / \         / \
      /   \          /   \         /   \       /   \
     9     7        9     3       9     2     4     7
    / \   / \      / \   / \     / \               / \
   1   4 6   8    1   4 6   2   1   4             6   2

5 8 5 5

/ \ / \ / \ / \

9 7 9 3 9 2 4 7

/ \ / \ / \ / \ / \ / \

1 4 6 8 1 4 6 2 1 4 6 2

se pueden representar por

   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))
   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int

ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))

ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)

ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

Definir la función

   igualEstructura :: Arbol -> Arbol -> Bool

1	igualEstructura :: Arbol -> Arbol -> Bool

tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,

   igualEstructura ej3arbol1 ej3arbol2 == True
   igualEstructura ej3arbol1 ej3arbol3 == False
   igualEstructura ej3arbol1 ej3arbol4 == False

igualEstructura ej3arbol1 ej3arbol2 == True

igualEstructura ej3arbol1 ej3arbol3 == False

igualEstructura ej3arbol1 ej3arbol4 == False

Soluciones

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

Soluciones en Haskell

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

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))
ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

igualEstructura :: Arbol a -> Arbol a -> Bool
igualEstructura (H _) (H _)             = True
igualEstructura (N _ i1 d1) (N _ i2 d2) =
  igualEstructura i1 i2 &&
  igualEstructura d1 d2
igualEstructura _ _                       = False

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int

ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))

ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)

ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

igualEstructura :: Arbol a -> Arbol a -> Bool

igualEstructura (H _) (H _) = True

igualEstructura (N _ i1 d1) (N _ i2 d2) =

igualEstructura i1 i2 &&

igualEstructura d1 d2

igualEstructura _ _ = False

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))
ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))
ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))
ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))

def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:
    match (a, b):
        case (H(_), H(_)):
            return True
        case (N(_, i1, d1), N(_, i2, d2)):
            return igualEstructura(i1, i2) and igualEstructura(d1, d2)
        case (_, _):
            return False
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))

ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))

ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))

ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))

def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:

match (a, b):

case (H(_), H(_)):

return True

case (N(_, i1, d1), N(_, i2, d2)):

return igualEstructura(i1, i2) and igualEstructura(d1, d2)

case (_, _):

return False

assert False

Árboles con bordes iguales

PorJosé A. Alonso 28-diciembre-202226-diciembre-2022

Los árboles binarios con valores en las hojas se pueden definir por

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

data Arbol a = H a

| N (Arbol a) (Arbol a)

deriving Show

Por ejemplo, los árboles

   árbol1          árbol2       árbol3     árbol4
      o              o           o           o
     / \            / \         / \         / \
    1   o          o   3       o   3       o   1
       / \        / \         / \         / \
      2   3      1   2       1   4       2   3

árbol1 árbol2 árbol3 árbol4

o o o o

/ \ / \ / \ / \

1 o o 3 o 3 o 1

/ \ / \ / \ / \

2 3 1 2 1 4 2 3

se representan por

   arbol1, arbol2, arbol3, arbol4 :: Arbol Int
   arbol1 = N (H 1) (N (H 2) (H 3))
   arbol2 = N (N (H 1) (H 2)) (H 3)
   arbol3 = N (N (H 1) (H 4)) (H 3)
   arbol4 = N (N (H 2) (H 3)) (H 1)

arbol1, arbol2, arbol3, arbol4 :: Arbol Int

arbol1 = N (H 1) (N (H 2) (H 3))

arbol2 = N (N (H 1) (H 2)) (H 3)

arbol3 = N (N (H 1) (H 4)) (H 3)

arbol4 = N (N (H 2) (H 3)) (H 1)

Definir la función

   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

1	igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,

   igualBorde arbol1 arbol2  ==  True
   igualBorde arbol1 arbol3  ==  False
   igualBorde arbol1 arbol4  ==  False

igualBorde arbol1 arbol2 == True

igualBorde arbol1 arbol3 == False

igualBorde arbol1 arbol4 == False

Soluciones

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

Soluciones en Haskell

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

arbol1, arbol2, arbol3, arbol4 :: Arbol Int
arbol1 = N (H 1) (N (H 2) (H 3))
arbol2 = N (N (H 1) (H 2)) (H 3)
arbol3 = N (N (H 1) (H 4)) (H 3)
arbol4 = N (N (H 2) (H 3)) (H 1)

igualBorde :: Eq a => Arbol a -> Arbol a -> Bool
igualBorde t1 t2 = borde t1 == borde t2

-- (borde t) es el borde del árbol t; es decir, la lista de las hojas
-- del árbol t leídas de izquierda a derecha. Por ejemplo,
--    borde arbol4  ==  [2,3,1]
borde :: Arbol a -> [a]
borde (N i d) = borde i ++ borde d
borde (H x)   = [x]

data Arbol a = N (Arbol a) (Arbol a)

| H a

deriving Show

arbol1, arbol2, arbol3, arbol4 :: Arbol Int

arbol1 = N (H 1) (N (H 2) (H 3))

arbol2 = N (N (H 1) (H 2)) (H 3)

arbol3 = N (N (H 1) (H 4)) (H 3)

arbol4 = N (N (H 2) (H 3)) (H 1)

igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

igualBorde t1 t2 = borde t1 == borde t2

-- (borde t) es el borde del árbol t; es decir, la lista de las hojas

-- del árbol t leídas de izquierda a derecha. Por ejemplo,

-- borde arbol4 == [2,3,1]

borde :: Arbol a -> [a]

borde (N i d) = borde i ++ borde d

borde (H x) = [x]

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]

arbol1: Arbol[int] = N(H(1), N(H(2), H(3)))
arbol2: Arbol[int] = N(N(H(1), H(2)), H(3))
arbol3: Arbol[int] = N(N(H(1), H(4)), H(3))
arbol4: Arbol[int] = N(N(H(2), H(3)), H(1))

# borde(t) es el borde del árbol t; es decir, la lista de las hojas
# del árbol t leídas de izquierda a derecha. Por ejemplo,
#    borde(arbol4)  ==  [2, 3, 1]
def borde(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(i, d):
            return borde(i) + borde(d)
    assert False

def igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool:
    return borde(t1) == borde(t2)

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

i: Arbol[A]

d: Arbol[A]

arbol1: Arbol[int] = N(H(1), N(H(2), H(3)))

arbol2: Arbol[int] = N(N(H(1), H(2)), H(3))

arbol3: Arbol[int] = N(N(H(1), H(4)), H(3))

arbol4: Arbol[int] = N(N(H(2), H(3)), H(1))

# borde(t) es el borde del árbol t; es decir, la lista de las hojas

# del árbol t leídas de izquierda a derecha. Por ejemplo,

# borde(arbol4) == [2, 3, 1]

def borde(a: Arbol[A]) -> list[A]:

match a:

case H(x):

return [x]

case N(i, d):

return borde(i) + borde(d)

assert False

def igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool:

return borde(t1) == borde(t2)

Árboles balanceados

PorJosé A. Alonso 27-diciembre-202226-diciembre-2022

Los árboles binarios con valores en los nodos se pueden definir por

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

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

/ \

8 6

/ \ / \

3 2 4 5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

1	N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.

Definir la función

   balanceado :: Arbol a -> Bool

1	balanceado :: Arbol a -> Bool

tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,

   λ> balanceado (N 5 H (N 3 H H))
   True
   λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))
   False

λ> balanceado (N 5 H (N 3 H H))

True

λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))

False

Soluciones

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

Soluciones en Haskell

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

balanceado :: Arbol a -> Bool
balanceado H         = True
balanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1
                       && balanceado i
                       && balanceado d

-- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo,
--    numeroNodos (N 5 H (N 3 H H)) ==  2
numeroNodos :: Arbol a -> Int
numeroNodos H         = 0
numeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos d

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

balanceado :: Arbol a -> Bool

balanceado H = True

balanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1

&& balanceado i

&& balanceado d

-- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo,

-- numeroNodos (N 5 H (N 3 H H)) == 2

numeroNodos :: Arbol a -> Int

numeroNodos H = 0

numeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos d

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    pass

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def numeroNodos(a: Arbol[A]) -> int:
    match a:
        case H():
            return 0
        case N(_, i, d):
            return 1 + numeroNodos(i) + numeroNodos(d)
    assert False

def balanceado(a: Arbol[A]) -> bool:
    match a:
        case H():
            return True
        case N(_, i, d):
            return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \
                and balanceado(i) and balanceado(d)
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

pass

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def numeroNodos(a: Arbol[A]) -> int:

match a:

case H():

return 0

case N(_, i, d):

return 1 + numeroNodos(i) + numeroNodos(d)

assert False

def balanceado(a: Arbol[A]) -> bool:

match a:

case H():

return True

case N(_, i, d):

return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \

and balanceado(i) and balanceado(d)

assert False

Rama izquierda de un árbol binario

PorJosé A. Alonso 26-diciembre-202225-diciembre-2022

Los árboles binarios con valores en los nodos se pueden definir por

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

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

/ \

8 6

/ \ / \

3 2 4 5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

1	N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir la función

   ramaIzquierda :: Arbol a -> [a]

1	ramaIzquierda :: Arbol a -> [a]

tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,

   λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H))
   [2,5,3]

1 2	λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) [2,5,3]

Soluciones

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

Soluciones en Haskell

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

ramaIzquierda :: Arbol a -> [a]
ramaIzquierda H         = []
ramaIzquierda (N x i _) = x : ramaIzquierda i

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

ramaIzquierda :: Arbol a -> [a]

ramaIzquierda H = []

ramaIzquierda (N x i _) = x : ramaIzquierda i

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    pass

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def ramaIzquierda(a: Arbol[A]) -> list[A]:
    match a:
        case H():
            return []
        case N(x, i, _):
            return [x] + ramaIzquierda(i)
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

pass

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def ramaIzquierda(a: Arbol[A]) -> list[A]:

match a:

case H():

return []

case N(x, i, _):

return [x] + ramaIzquierda(i)

assert False

Suma de un árbol

PorJosé A. Alonso 23-diciembre-202225-diciembre-2022

Los árboles binarios con valores en los nodos se pueden definir por

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

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

/ \

8 6

/ \ / \

3 2 4 5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

1	N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir por recursión la función

   sumaArbol :: Num a => Arbol1 a -> a

1	sumaArbol :: Num a => Arbol1 a -> a

tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,

   sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21

1	sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21

Soluciones

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

Soluciones en Haskell

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

sumaArbol :: Num a => Arbol1 a -> a
sumaArbol H         = 0
sumaArbol (N x i d) = x + sumaArbol i + sumaArbol d

data Arbol1 a = H

| N a (Arbol1 a) (Arbol1 a)

deriving (Show, Eq)

sumaArbol :: Num a => Arbol1 a -> a

sumaArbol H = 0

sumaArbol (N x i d) = x + sumaArbol i + sumaArbol d

Soluciones en Python

from dataclasses import dataclass

@dataclass
class Arbol:
    pass

@dataclass
class H(Arbol):
    pass

@dataclass
class N(Arbol):
    x: int
    i: Arbol
    d: Arbol

def sumaArbol(a: Arbol) -> int:
    match a:
        case H():
            return 0
        case N(x, i, d):
            return x + sumaArbol(i) + sumaArbol(d)
    assert False

from dataclasses import dataclass

@dataclass

class Arbol:

pass

@dataclass

class H(Arbol):

pass

@dataclass

class N(Arbol):

x: int

i: Arbol

d: Arbol

def sumaArbol(a: Arbol) -> int:

match a:

case H():

return 0

case N(x, i, d):

return x + sumaArbol(i) + sumaArbol(d)

assert False

El tipo de los árboles binarios con valores en los nodos

PorJosé A. Alonso 23-diciembre-202224-abril-2023

1. El tipo de los árboles binarios con valores en los nodos en Haskell

El árbol, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

/ \

8 6

/ \ / \

3 2 4 5

/\ /\ /\ /\

· ·· ·· · · ·

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

1	N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.

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

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

2. El tipo de los árboles binarios con valores en los nodos en Python

El árbol binario, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

/ \

8 6

/ \ / \

3 2 4 5

/\ /\ /\ /\

· ·· ·· · · ·

se puede representar por

   N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))

1	N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))

usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    pass

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

pass

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

Árbol de profundidad n con nodos iguales

PorJosé A. Alonso 22-diciembre-202220-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Definir las funciones

   repeatArbol    :: a -> Arbol a
   replicateArbol :: Int -> a -> Arbol a

1 2	repeatArbol :: a -> Arbol a replicateArbol :: Int -> a -> Arbol a

tales que

repeatArbol x es es árbol con infinitos nodos x. Por ejemplo,

     takeArbol 0 (repeatArbol 3) == H 3
     takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
     takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))

takeArbol 0 (repeatArbol 3) == H 3

takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)

takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))

replicate n x es el árbol de profundidad n cuyos nodos son x. Por ejemplo,

     replicateArbol 0 5  ==  H 5
     replicateArbol 1 5  ==  N 5 (H 5) (H 5)
     replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))

replicateArbol 0 5 == H 5

replicateArbol 1 5 == N 5 (H 5) (H 5)

replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))

Comprobar con QuickCheck que el número de hojas de replicateArbol n x es 2^n, para todo número natural n.
Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

repeatArbol :: a -> Arbol a
repeatArbol x = N x t t
  where t = repeatArbol x

replicateArbol :: Int -> a -> Arbol a
replicateArbol n = takeArbol n . repeatArbol

-- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo,
--    takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
--    takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
--    takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
--    takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
takeArbol :: Int -> Arbol a -> Arbol a
takeArbol _ (H x)     = H x
takeArbol 0 (N x _ _) = H x
takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)

-- Generador para las comprobaciones
-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    N 0 (H 0) (H 0)
--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)
--    N 3 (H 1) (H 2)
--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
--    H 7
--    N (-8) (H (-8)) (H 9)
--    H 2
--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
--    H (-3)
--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)
--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
  oneof [H <$> arbitrary,
         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario

-- Función auxiliar para la comprobación
-- =====================================

-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3
nHojas :: Arbol a -> Int
nHojas (H _)     = 1
nHojas (N _ i d) = nHojas i + nHojas d

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_replicateArbol :: Int -> Int -> Property
prop_replicateArbol n x =
  n >= 0 ==> nHojas (replicateArbol n x) == 2^n

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
--    +++ OK, passed 100 tests.

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

repeatArbol :: a -> Arbol a

repeatArbol x = N x t t

where t = repeatArbol x

replicateArbol :: Int -> a -> Arbol a

replicateArbol n = takeArbol n . repeatArbol

-- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo,

-- takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9

-- takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)

-- takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

-- takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

takeArbol :: Int -> Arbol a -> Arbol a

takeArbol _ (H x) = H x

takeArbol 0 (N x _ _) = H x

takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)

-- Generador para las comprobaciones

-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,

-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))

-- N 0 (H 0) (H 0)

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

-- N 3 (H 1) (H 2)

-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))

-- H 7

-- N (-8) (H (-8)) (H 9)

-- H 2

-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))

-- H (-3)

-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)

-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))

arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)

arbolArbitrario 0 = H <$> arbitrary

arbolArbitrario n =

oneof [H <$> arbitrary,

N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbolArbitrario

-- Función auxiliar para la comprobación

-- =====================================

-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,

-- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3

nHojas :: Arbol a -> Int

nHojas (H _) = 1

nHojas (N _ i d) = nHojas i + nHojas d

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_replicateArbol :: Int -> Int -> Property

prop_replicateArbol n x =

n >= 0 ==> nHojas (replicateArbol n x) == 2^n

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol

-- +++ OK, passed 100 tests.

Soluciones en Python

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def replicateArbol(n: int, x: A) -> Arbol[A]:
    match n:
        case 0:
            return H(x)
        case n:
            t = replicateArbol(n - 1, x)
            return N(x, t, t)
    assert False

# Generador para las comprobaciones
# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
#    >>> arbolArbitrario(4)
#    N(x=2, i=H(x=1), d=H(x=9))
#    >>> arbolArbitrario(4)
#    H(x=10)
#    >>> arbolArbitrario(4)
#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return H(randint(0, 10))
    m = n // 2
    return choice([H(randint(0, 10)),
                   N(randint(0, 10),
                     arbolArbitrario(m),
                     arbolArbitrario(m))])

# Función auxiliar para la comprobación
# =====================================

# nHojas(x) es el número de hojas del árbol x. Por ejemplo,
#    nHojas(N(9, N(3, H(2), H(4)), H(7)))  ==  3
def nHojas(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 1
        case N(_, i, d):
            return nHojas(i) + nHojas(d)
    assert False

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_nHojas(n: int, x: int) -> None:
    assert nHojas(replicateArbol(n, x)) == 2**n

# La comprobación es
#    src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py
#    1 passed in 0.20s

from dataclasses import dataclass

from random import choice, randint

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def replicateArbol(n: int, x: A) -> Arbol[A]:

match n:

case 0:

return H(x)

case n:

t = replicateArbol(n - 1, x)

return N(x, t, t)

assert False

# Generador para las comprobaciones

# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,

# >>> arbolArbitrario(4)

# N(x=2, i=H(x=1), d=H(x=9))

# >>> arbolArbitrario(4)

# H(x=10)

# >>> arbolArbitrario(4)

# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))

def arbolArbitrario(n: int) -> Arbol[int]:

if n <= 1:

return H(randint(0, 10))

m = n // 2

return choice([H(randint(0, 10)),

N(randint(0, 10),

arbolArbitrario(m),

arbolArbitrario(m))])

# Función auxiliar para la comprobación

# =====================================

# nHojas(x) es el número de hojas del árbol x. Por ejemplo,

# nHojas(N(9, N(3, H(2), H(4)), H(7))) == 3

def nHojas(a: Arbol[A]) -> int:

match a:

case H(_):

return 1

case N(_, i, d):

return nHojas(i) + nHojas(d)

assert False

# Comprobación de la propiedad

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=10),

st.integers(min_value=1, max_value=10))

def test_nHojas(n: int, x: int) -> None:

assert nHojas(replicateArbol(n, x)) == 2**n

# La comprobación es

# src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py

# 1 passed in 0.20s

Subárbol de profundidad dada

PorJosé A. Alonso 21-diciembre-202220-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

La función take está definida por

   take :: Int -> [a] -> [a]
   take 0            = []
   take (n+1) []     = []
   take (n+1) (x:xs) = x : take n xs

take :: Int -> [a] -> [a]

take 0 = []

take (n+1) [] = []

take (n+1) (x:xs) = x : take n xs

Definir la función

   takeArbol ::  Int -> Arbol a -> Arbol a

1	takeArbol :: Int -> Arbol a -> Arbol a

tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,

   takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
   takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
   takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
   takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9

takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)

takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

takeArbol :: Int -> Arbol a -> Arbol a
takeArbol _ (H x)     = H x
takeArbol 0 (N x _ _) = H x
takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)

-- Generador para las comprobaciones
-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    N 0 (H 0) (H 0)
--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)
--    N 3 (H 1) (H 2)
--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
--    H 7
--    N (-8) (H (-8)) (H 9)
--    H 2
--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
--    H (-3)
--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)
--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
  oneof [H <$> arbitrary,
         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario

-- Función auxiliar para la comprobación
-- =====================================

-- (profundidad x) es la profundidad del árbol x. Por ejemplo,
--    profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2
--    profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3
--    profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2
profundidad :: Arbol a -> Int
profundidad (H _)     = 0
profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_takeArbol :: Int -> Arbol Int -> Property
prop_takeArbol n x =
  n >= 0 ==> profundidad (takeArbol n x) <= n

-- La comprobación es
--    λ> quickCheck prop_takeArbol
--    +++ OK, passed 100 tests.

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

takeArbol :: Int -> Arbol a -> Arbol a

takeArbol _ (H x) = H x

takeArbol 0 (N x _ _) = H x

takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)

-- Generador para las comprobaciones

-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,

-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))

-- N 0 (H 0) (H 0)

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

-- N 3 (H 1) (H 2)

-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))

-- H 7

-- N (-8) (H (-8)) (H 9)

-- H 2

-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))

-- H (-3)

-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)

-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))

arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)

arbolArbitrario 0 = H <$> arbitrary

arbolArbitrario n =

oneof [H <$> arbitrary,

N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbolArbitrario

-- Función auxiliar para la comprobación

-- =====================================

-- (profundidad x) es la profundidad del árbol x. Por ejemplo,

-- profundidad (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2

-- profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7)) == 3

-- profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4))) == 2

profundidad :: Arbol a -> Int

profundidad (H _) = 0

profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_takeArbol :: Int -> Arbol Int -> Property

prop_takeArbol n x =

n >= 0 ==> profundidad (takeArbol n x) <= n

-- La comprobación es

-- λ> quickCheck prop_takeArbol

-- +++ OK, passed 100 tests.

Soluciones en Python

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def takeArbol(n: int, a: Arbol[A]) -> Arbol[A]:
    match (n, a):
        case (_, H(x)):
            return H(x)
        case (0, N(x, _, _)):
            return H(x)
        case (n, N(x, i, d)):
            return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d))
    assert False

# Generador para las comprobaciones
# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
#    >>> arbolArbitrario(4)
#    N(x=2, i=H(x=1), d=H(x=9))
#    >>> arbolArbitrario(4)
#    H(x=10)
#    >>> arbolArbitrario(4)
#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return H(randint(0, 10))
    m = n // 2
    return choice([H(randint(0, 10)),
                   N(randint(0, 10),
                     arbolArbitrario(m),
                     arbolArbitrario(m))])

# Función auxiliar para la comprobación
# =====================================

# profundidad(x) es la profundidad del árbol x. Por ejemplo,
#    profundidad(N(9, N(3, H(2), H(4)), H(7)))              ==  2
#    profundidad(N(9, N(3, H(2), N(1, H(4), H(5))), H(7)))  ==  3
#    profundidad(N(4, N(5, H(4), H(2)), N(3, H(7), H(4))))  ==  2
def profundidad(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 0
        case N(_, i, d):
            return 1 + max(profundidad(i), profundidad(d))
    assert False

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=12),
       st.integers(min_value=1, max_value=10))
def test_takeArbol(n: int, m: int) -> None:
    x = arbolArbitrario(m)
    assert profundidad(takeArbol(n, x)) <= n

# La comprobación es
#    src> poetry run pytest -q subarbol_de_profundidad_dada.py
#    1 passed in 0.23s

from dataclasses import dataclass

from random import choice, randint

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def takeArbol(n: int, a: Arbol[A]) -> Arbol[A]:

match (n, a):

case (_, H(x)):

return H(x)

case (0, N(x, _, _)):

return H(x)

case (n, N(x, i, d)):

return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d))

assert False

# Generador para las comprobaciones

# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,

# >>> arbolArbitrario(4)

# N(x=2, i=H(x=1), d=H(x=9))

# >>> arbolArbitrario(4)

# H(x=10)

# >>> arbolArbitrario(4)

# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))

def arbolArbitrario(n: int) -> Arbol[int]:

if n <= 1:

return H(randint(0, 10))

m = n // 2

return choice([H(randint(0, 10)),

N(randint(0, 10),

arbolArbitrario(m),

arbolArbitrario(m))])

# Función auxiliar para la comprobación

# =====================================

# profundidad(x) es la profundidad del árbol x. Por ejemplo,

# profundidad(N(9, N(3, H(2), H(4)), H(7))) == 2

# profundidad(N(9, N(3, H(2), N(1, H(4), H(5))), H(7))) == 3

# profundidad(N(4, N(5, H(4), H(2)), N(3, H(7), H(4)))) == 2

def profundidad(a: Arbol[A]) -> int:

match a:

case H(_):

return 0

case N(_, i, d):

return 1 + max(profundidad(i), profundidad(d))

assert False

# Comprobación de la propiedad

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=12),

st.integers(min_value=1, max_value=10))

def test_takeArbol(n: int, m: int) -> None:

x = arbolArbitrario(m)

assert profundidad(takeArbol(n, x)) <= n

# La comprobación es

# src> poetry run pytest -q subarbol_de_profundidad_dada.py

# 1 passed in 0.23s

Imagen especular de un árbol binario

PorJosé A. Alonso 20-diciembre-202219-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Definir la función

   espejo :: Arbol a -> Arbol a

1	espejo :: Arbol a -> Arbol a

tal que espejo x es la imagen especular del árbol x. Por ejemplo,

   espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))

1	espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))

Comprobar con QuickCheck las siguientes propiedades, para todo árbol x,

   espejo (espejo x) = x
   reverse (preorden (espejo x)) = postorden x
   postorden (espejo x) = reverse (preorden x)

espejo (espejo x) = x

reverse (preorden (espejo x)) = postorden x

postorden (espejo x) = reverse (preorden x)

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

espejo :: Arbol a -> Arbol a
espejo (H x)     = H x
espejo (N x i d) = N x (espejo d) (espejo i)

-- Generador para las comprobaciones
-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    N 0 (H 0) (H 0)
--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)
--    N 3 (H 1) (H 2)
--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
--    H 7
--    N (-8) (H (-8)) (H 9)
--    H 2
--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
--    H (-3)
--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)
--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
  oneof [H <$> arbitrary,
         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario

-- Funciones auxiliares para la comprobación
-- =========================================

-- (preorden x) es la lista correspondiente al recorrido preorden del
-- árbol x; es decir, primero visita la raíz del árbol, a continuación
-- recorre el subárbol izquierdo y, finalmente, recorre el subárbol
-- derecho. Por ejemplo,
--    preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
preorden :: Arbol a -> [a]
preorden (H x)     = [x]
preorden (N x i d) = x : preorden i ++ preorden d

-- (postorden x) es la lista correspondiente al recorrido postorden
-- del árbol x; es decir, primero recorre el subárbol izquierdo, a
-- continuación el subárbol derecho y, finalmente, la raíz del
-- árbol. Por ejemplo,
--    postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]
postorden :: Arbol a -> [a]
postorden (H x)     = [x]
postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de las propiedades
-- ===============================

-- Las propiedades son
prop_espejo :: Arbol Int -> Bool
prop_espejo x =
  espejo (espejo x) == x &&
  reverse (preorden (espejo x)) == postorden x &&
  postorden (espejo x) == reverse (preorden x)

-- La comprobación es
--    λ> quickCheck prop_espejo
--    OK, passed 100 tests.

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

espejo :: Arbol a -> Arbol a

espejo (H x) = H x

espejo (N x i d) = N x (espejo d) (espejo i)

-- Generador para las comprobaciones

-- =================================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,

-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))

-- N 0 (H 0) (H 0)

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

-- N 3 (H 1) (H 2)

-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))

-- H 7

-- N (-8) (H (-8)) (H 9)

-- H 2

-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))

-- H (-3)

-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)

-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))

arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)

arbolArbitrario 0 = H <$> arbitrary

arbolArbitrario n =

oneof [H <$> arbitrary,

N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbolArbitrario

-- Funciones auxiliares para la comprobación

-- =========================================

-- (preorden x) es la lista correspondiente al recorrido preorden del

-- árbol x; es decir, primero visita la raíz del árbol, a continuación

-- recorre el subárbol izquierdo y, finalmente, recorre el subárbol

-- derecho. Por ejemplo,

-- preorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [9,3,2,4,7]

preorden :: Arbol a -> [a]

preorden (H x) = [x]

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

-- (postorden x) es la lista correspondiente al recorrido postorden

-- del árbol x; es decir, primero recorre el subárbol izquierdo, a

-- continuación el subárbol derecho y, finalmente, la raíz del

-- árbol. Por ejemplo,

-- postorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,4,3,7,9]

postorden :: Arbol a -> [a]

postorden (H x) = [x]

postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de las propiedades

-- ===============================

-- Las propiedades son

prop_espejo :: Arbol Int -> Bool

prop_espejo x =

espejo (espejo x) == x &&

reverse (preorden (espejo x)) == postorden x &&

postorden (espejo x) == reverse (preorden x)

-- La comprobación es

-- λ> quickCheck prop_espejo

-- OK, passed 100 tests.

Soluciones en Python

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def espejo(a: Arbol[A]) -> Arbol[A]:
    match a:
        case H(x):
            return H(x)
        case N(x, i, d):
            return N(x, espejo(d), espejo(i))
    assert False

# Generador para las comprobaciones
# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
#    >>> arbolArbitrario(4)
#    N(x=2, i=H(x=1), d=H(x=9))
#    >>> arbolArbitrario(4)
#    H(x=10)
#    >>> arbolArbitrario(4)
#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return H(randint(0, 10))
    m = n // 2
    return choice([H(randint(0, 10)),
                   N(randint(0, 10),
                     arbolArbitrario(m),
                     arbolArbitrario(m))])

# Funciones auxiliares para la comprobación
# =========================================

# preorden(x) es la lista correspondiente al recorrido preorden del
# árbol x; es decir, primero visita la raíz del árbol, a continuación
# recorre el subárbol izquierdo y, finalmente, recorre el subárbol
# derecho. Por ejemplo,
#    >>> preorden(N(9, N(3, H(2), H(4)), H(7)))
#    [9, 3, 2, 4, 7]
def preorden(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(x, i, d):
            return [x] + preorden(i) + preorden(d)
    assert False

# (postorden x) es la lista correspondiente al recorrido postorden
# del árbol x; es decir, primero recorre el subárbol izquierdo, a
# continuación el subárbol derecho y, finalmente, la raíz del
# árbol. Por ejemplo,
#    >>> postorden(N(9, N(3, H(2), H(4)), H(7)))
#    [2, 4, 3, 7, 9]
def postorden(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(x, i, d):
            return postorden(i) + postorden(d) + [x]
    assert False

# Comprobación de las propiedades
# ===============================

# Las propiedades son
@given(st.integers(min_value=1, max_value=10))
def test_espejo(n: int) -> None:
    x = arbolArbitrario(n)
    assert espejo(espejo(x)) == x
    assert list(reversed(preorden(espejo(x)))) == postorden(x)
    assert postorden(espejo(x)) == list(reversed(preorden(x)))

# La comprobación es
#    src> poetry run pytest -q imagen_especular_de_un_arbol_binario.py
#    1 passed in 0.16s

from dataclasses import dataclass

from random import choice, randint

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def espejo(a: Arbol[A]) -> Arbol[A]:

match a:

case H(x):

return H(x)

case N(x, i, d):

return N(x, espejo(d), espejo(i))

assert False

# Generador para las comprobaciones

# =================================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,

# >>> arbolArbitrario(4)

# N(x=2, i=H(x=1), d=H(x=9))

# >>> arbolArbitrario(4)

# H(x=10)

# >>> arbolArbitrario(4)

# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))

def arbolArbitrario(n: int) -> Arbol[int]:

if n <= 1:

return H(randint(0, 10))

m = n // 2

return choice([H(randint(0, 10)),

N(randint(0, 10),

arbolArbitrario(m),

arbolArbitrario(m))])

# Funciones auxiliares para la comprobación

# =========================================

# preorden(x) es la lista correspondiente al recorrido preorden del

# árbol x; es decir, primero visita la raíz del árbol, a continuación

# recorre el subárbol izquierdo y, finalmente, recorre el subárbol

# derecho. Por ejemplo,

# >>> preorden(N(9, N(3, H(2), H(4)), H(7)))

# [9, 3, 2, 4, 7]

def preorden(a: Arbol[A]) -> list[A]:

match a:

case H(x):

return [x]

case N(x, i, d):

return [x] + preorden(i) + preorden(d)

assert False

# (postorden x) es la lista correspondiente al recorrido postorden

# del árbol x; es decir, primero recorre el subárbol izquierdo, a

# continuación el subárbol derecho y, finalmente, la raíz del

# árbol. Por ejemplo,

# >>> postorden(N(9, N(3, H(2), H(4)), H(7)))

# [2, 4, 3, 7, 9]

def postorden(a: Arbol[A]) -> list[A]:

match a:

case H(x):

return [x]

case N(x, i, d):

return postorden(i) + postorden(d) + [x]

assert False

# Comprobación de las propiedades

# ===============================

# Las propiedades son

@given(st.integers(min_value=1, max_value=10))

def test_espejo(n: int) -> None:

x = arbolArbitrario(n)

assert espejo(espejo(x)) == x

assert list(reversed(preorden(espejo(x)))) == postorden(x)

assert postorden(espejo(x)) == list(reversed(preorden(x)))

# La comprobación es

# src> poetry run pytest -q imagen_especular_de_un_arbol_binario.py

# 1 passed in 0.16s

Recorrido de árboles binarios

PorJosé A. Alonso 19-diciembre-202218-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

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

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Definir las funciones

   preorden  :: Arbol a -> [a]
   postorden :: Arbol a -> [a]

1 2	preorden :: Arbol a -> [a] postorden :: Arbol a -> [a]

tales que

preorden es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,

     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]

1	preorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [9,3,2,4,7]

postorden x es la lista correspondiente al recorrido postorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación el subárbol derecho y, finalmente, la raíz del árbol. Por ejemplo,

     postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]

1	postorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,4,3,7,9]

Comprobar con QuickCheck que la longitud de la lista obtenida recorriendo un árbol en cualquiera de los sentidos es igual al número de nodos del árbol más el número de hojas.
Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

preorden :: Arbol a -> [a]
preorden (H x)     = [x]
preorden (N x i d) = x : preorden i ++ preorden d

postorden :: Arbol a -> [a]
postorden (H x)     = [x]
postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de la propiedad
-- ============================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    N 0 (H 0) (H 0)
--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)
--    N 3 (H 1) (H 2)
--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
--    H 7
--    N (-8) (H (-8)) (H 9)
--    H 2
--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
--    H (-3)
--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)
--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
  oneof [H <$> arbitrary,
         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario

-- La propiedad es
prop_longitud_recorrido :: Arbol Int -> Bool
prop_longitud_recorrido x =
   length (preorden x)  == n &&
   length (postorden x) == n
   where n = nNodos x + nHojas x

-- (nNodos x) es el número de nodos del árbol x. Por ejemplo,
--      nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2
nNodos :: Arbol a -> Int
nNodos (H _)     = 0
nNodos (N _ i d) = 1 + nNodos i + nNodos d

-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3
nHojas :: Arbol a -> Int
nHojas (H _)     = 1
nHojas (N _ i d) = nHojas i + nHojas d

-- La comprobación es
--    λ> quickCheck prop_longitud_recorrido
--    OK, passed 100 tests.

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

preorden :: Arbol a -> [a]

preorden (H x) = [x]

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

postorden :: Arbol a -> [a]

postorden (H x) = [x]

postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de la propiedad

-- ============================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,

-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))

-- N 0 (H 0) (H 0)

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

-- N 3 (H 1) (H 2)

-- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))

-- H 7

-- N (-8) (H (-8)) (H 9)

-- H 2

-- N (-1) (H 7) (N 9 (H (-2)) (H (-8)))

-- H (-3)

-- N 0 (N 16 (H (-14)) (H (-18))) (H 7)

-- N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))

arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)

arbolArbitrario 0 = H <$> arbitrary

arbolArbitrario n =

oneof [H <$> arbitrary,

N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbolArbitrario

-- La propiedad es

prop_longitud_recorrido :: Arbol Int -> Bool

prop_longitud_recorrido x =

length (preorden x) == n &&

length (postorden x) == n

where n = nNodos x + nHojas x

-- (nNodos x) es el número de nodos del árbol x. Por ejemplo,

-- nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2

nNodos :: Arbol a -> Int

nNodos (H _) = 0

nNodos (N _ i d) = 1 + nNodos i + nNodos d

-- (nHojas x) es el número de hojas del árbol x. Por ejemplo,

-- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3

nHojas :: Arbol a -> Int

nHojas (H _) = 1

nHojas (N _ i d) = nHojas i + nHojas d

-- La comprobación es

-- λ> quickCheck prop_longitud_recorrido

-- OK, passed 100 tests.

Soluciones en Python

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def preorden(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(x, i, d):
            return [x] + preorden(i) + preorden(d)
    assert False

def postorden(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(x, i, d):
            return postorden(i) + postorden(d) + [x]
    assert False

# Comprobación de la propiedad
# ============================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
#    >>> arbolArbitrario(4)
#    N(x=2, i=H(x=1), d=H(x=9))
#    >>> arbolArbitrario(4)
#    H(x=10)
#    >>> arbolArbitrario(4)
#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return H(randint(0, 10))
    m = n // 2
    return choice([H(randint(0, 10)),
                   N(randint(0, 10),
                     arbolArbitrario(m),
                     arbolArbitrario(m))])

# nNodos(x) es el número de nodos del árbol x. Por ejemplo,
#    nNodos(N(9, N(3, H(2), H(4)), H(7)))  ==  2
def nNodos(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 0
        case N(_, i, d):
            return 1 + nNodos(i) + nNodos(d)
    assert False

# (nHojas x) es el número de hojas del árbol x. Por ejemplo,
#    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3
def nHojas(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 1
        case N(_, i, d):
            return nHojas(i) + nHojas(d)
    assert False

# La propiedad es
@given(st.integers(min_value=1, max_value=10))
def test_recorrido(n: int) -> None:
    a = arbolArbitrario(n)
    m = nNodos(a) + nHojas(a)
    assert len(preorden(a)) == m
    assert len(postorden(a)) == m

# La comprobación es
#    src> poetry run pytest -q recorrido_de_arboles_binarios.py
#    1 passed in 0.16s

from dataclasses import dataclass

from random import choice, randint

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

def preorden(a: Arbol[A]) -> list[A]:

match a:

case H(x):

return [x]

case N(x, i, d):

return [x] + preorden(i) + preorden(d)

assert False

def postorden(a: Arbol[A]) -> list[A]:

match a:

case H(x):

return [x]

case N(x, i, d):

return postorden(i) + postorden(d) + [x]

assert False

# Comprobación de la propiedad

# ============================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,

# >>> arbolArbitrario(4)

# N(x=2, i=H(x=1), d=H(x=9))

# >>> arbolArbitrario(4)

# H(x=10)

# >>> arbolArbitrario(4)

# N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))

def arbolArbitrario(n: int) -> Arbol[int]:

if n <= 1:

return H(randint(0, 10))

m = n // 2

return choice([H(randint(0, 10)),

N(randint(0, 10),

arbolArbitrario(m),

arbolArbitrario(m))])

# nNodos(x) es el número de nodos del árbol x. Por ejemplo,

# nNodos(N(9, N(3, H(2), H(4)), H(7))) == 2

def nNodos(a: Arbol[A]) -> int:

match a:

case H(_):

return 0

case N(_, i, d):

return 1 + nNodos(i) + nNodos(d)

assert False

# (nHojas x) es el número de hojas del árbol x. Por ejemplo,

# nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3

def nHojas(a: Arbol[A]) -> int:

match a:

case H(_):

return 1

case N(_, i, d):

return nHojas(i) + nHojas(d)

assert False

# La propiedad es

@given(st.integers(min_value=1, max_value=10))

def test_recorrido(n: int) -> None:

a = arbolArbitrario(n)

m = nNodos(a) + nHojas(a)

assert len(preorden(a)) == m

assert len(postorden(a)) == m

# La comprobación es

# src> poetry run pytest -q recorrido_de_arboles_binarios.py

# 1 passed in 0.16s

1. El tipo abstracto de datos de las pilas

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

2.2. Implementación de las pilas mediante listas

2.3. Implementación de las pilas mediante sucesiones

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

3.2. Implementación de las pilas mediante listas

3.3. Implementación de las pilas mediante deque

1. El tipo de las expresiones aritméticas con variables en Haskell

2. El tipo de las expresiones aritméticas con variables en Python

1. El tipo de las expresiones aritméticas con una variable en Haskell

2. El tipo de las expresiones aritméticas con una variable en Python

1. El tipo de las expresiones aritméticas básicas en Haskell

2. El tipo de las expresiones aritméticas básicas en Python

1. El tipo de los árboles binarios con valores en los nodos en Haskell

2. El tipo de los árboles binarios con valores en los nodos en Python

Entradas recientes

Buscar

Correo electrónico