8-diciembre-2022 – Exercitium

Árboles con la misma forma

PorJosé A. Alonso 8-diciembre-202214-diciembre-2022

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

/ \

· ·

/ \ / \

1 4 6 9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

1 2	ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

deriving (Show, Eq)

Definir la función

   mismaForma :: Arbol a -> Arbol b -> Bool

1	mismaForma :: Arbol a -> Arbol b -> Bool

tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,

   λ> arbol1 = Hoja 5
   λ> arbol2 = Hoja 3
   λ> mismaForma arbol1 arbol2
   True
   λ> arbol3 = Nodo (Hoja 6) (Hoja 7)
   λ> mismaForma arbol1 arbol3
   False
   λ> arbol4 = Nodo (Hoja 9) (Hoja 5)
   λ> mismaForma arbol3 arbol4
   True

λ> arbol1 = Hoja 5

λ> arbol2 = Hoja 3

λ> mismaForma arbol1 arbol2

True

λ> arbol3 = Nodo (Hoja 6) (Hoja 7)

λ> mismaForma arbol1 arbol3

False

λ> arbol4 = Nodo (Hoja 9) (Hoja 5)

λ> mismaForma arbol3 arbol4

True

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
  deriving (Show, Eq)

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

mismaForma1 :: Arbol a -> Arbol b -> Bool
mismaForma1 (Hoja _)   (Hoja _)     = True
mismaForma1 (Nodo l r) (Nodo l' r') = mismaForma1 l l' && mismaForma1 r r'
mismaForma1 _          _            = False

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

mismaForma2 :: Arbol a -> Arbol b -> Bool
mismaForma2 x y = f x == f y
  where
    f = mapArbol (const ())

-- (mapArbol f t) es el árbol obtenido aplicando la función f a los
-- elementos del árbol t. Por ejemplo,
--    λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))
--    Nodo (Hoja 3) (Hoja 5)
mapArbol :: (a -> b) -> Arbol a -> Arbol b
mapArbol f (Hoja a)   = Hoja (f a)
mapArbol f (Nodo i d) = Nodo (mapArbol f i) (mapArbol f d)

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

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    Nodo (Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)) (Hoja 0)
--    Nodo (Nodo (Hoja 4) (Hoja 8)) (Hoja (-4))
--    Nodo (Nodo (Nodo (Hoja 4) (Hoja 10)) (Hoja (-6))) (Hoja (-1))
--    Nodo (Nodo (Hoja 3) (Hoja 6)) (Hoja (-5))
--    Nodo (Nodo (Hoja (-11)) (Hoja (-13))) (Hoja 14)
--    Nodo (Nodo (Hoja (-7)) (Hoja 15)) (Hoja (-2))
--    Nodo (Nodo (Hoja (-9)) (Hoja (-2))) (Hoja (-6))
--    Nodo (Nodo (Hoja (-15)) (Hoja (-16))) (Hoja (-20))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario n
  | n <= 1    = Hoja <$> arbitrary
  | otherwise = do
      k <- choose (2, n - 1)
      Nodo <$> arbolArbitrario k <*> arbolArbitrario (n - k)

-- Arbol es subclase de Arbitraria
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario
  shrink (Hoja x)   = Hoja <$> shrink x
  shrink (Nodo l r) = l :
                      r :
                      [Nodo l' r | l' <- shrink l] ++
                      [Nodo l r' | r' <- shrink r]

-- La propiedad es
prop_mismaForma :: Arbol Int -> Arbol Int -> Property
prop_mismaForma a1 a2 =
  mismaForma1 a1 a2 === mismaForma2 a1 a2

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

import Test.QuickCheck

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

deriving (Show, Eq)

-- 1ª solución

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

mismaForma1 :: Arbol a -> Arbol b -> Bool

mismaForma1 (Hoja _) (Hoja _) = True

mismaForma1 (Nodo l r) (Nodo l' r') = mismaForma1 l l' && mismaForma1 r r'

mismaForma1 _ _ = False

-- 2ª solución

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

mismaForma2 :: Arbol a -> Arbol b -> Bool

mismaForma2 x y = f x == f y

where

f = mapArbol (const ())

-- (mapArbol f t) es el árbol obtenido aplicando la función f a los

-- elementos del árbol t. Por ejemplo,

-- λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))

-- Nodo (Hoja 3) (Hoja 5)

mapArbol :: (a -> b) -> Arbol a -> Arbol b

mapArbol f (Hoja a) = Hoja (f a)

mapArbol f (Nodo i d) = Nodo (mapArbol f i) (mapArbol f d)

-- Comprobación de equivalencia

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

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,

-- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))

-- Nodo (Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)) (Hoja 0)

-- Nodo (Nodo (Hoja 4) (Hoja 8)) (Hoja (-4))

-- Nodo (Nodo (Nodo (Hoja 4) (Hoja 10)) (Hoja (-6))) (Hoja (-1))

-- Nodo (Nodo (Hoja 3) (Hoja 6)) (Hoja (-5))

-- Nodo (Nodo (Hoja (-11)) (Hoja (-13))) (Hoja 14)

-- Nodo (Nodo (Hoja (-7)) (Hoja 15)) (Hoja (-2))

-- Nodo (Nodo (Hoja (-9)) (Hoja (-2))) (Hoja (-6))

-- Nodo (Nodo (Hoja (-15)) (Hoja (-16))) (Hoja (-20))

arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)

arbolArbitrario n

| n <= 1 = Hoja <$> arbitrary

| otherwise = do

k <- choose (2, n - 1)

Nodo <$> arbolArbitrario k <*> arbolArbitrario (n - k)

-- Arbol es subclase de Arbitraria

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbolArbitrario

shrink (Hoja x) = Hoja <$> shrink x

shrink (Nodo l r) = l :

r :

[Nodo l' r | l' <- shrink l] ++

[Nodo l r' | r' <- shrink r]

-- La propiedad es

prop_mismaForma :: Arbol Int -> Arbol Int -> Property

prop_mismaForma a1 a2 =

mismaForma1 a1 a2 === mismaForma2 a1 a2

-- La comprobación es

-- λ> quickCheck prop_mismaForma

-- +++ OK, passed 100 tests.

Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar("A")
B = TypeVar("B")

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

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

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

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

def mismaForma1(a: Arbol[A], b: Arbol[B]) -> bool:
    match (a, b):
        case (Hoja(_), Hoja(_)):
            return True
        case (Nodo(i1, d1), Nodo(i2, d2)):
            return mismaForma1(i1, i2) and mismaForma1(d1, d2)
        case (_, _):
            return False
    assert False

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

# mapArbol(f, t) es el árbolo obtenido aplicando la función f a
# los elementos del árbol t. Por ejemplo,
#    >>> mapArbol(lambda x: 1 + x, Nodo(Hoja(2), Hoja(4)))
#    Nodo(i=Hoja(x=3), d=Hoja(x=5))
def mapArbol(f: Callable[[A], B], a: Arbol[A]) -> Arbol[B]:
    match a:
        case Hoja(x):
            return Hoja(f(x))
        case Nodo(i, d):
            return Nodo(mapArbol(f, i), mapArbol(f, d))
    assert False

def mismaForma2(a: Arbol[A], b: Arbol[B]) -> bool:
    return mapArbol(lambda x: 0, a) == mapArbol(lambda x: 0, b)

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

# arbolArbitrario(n) es un árbol aleatorio de altura n. Por ejemplo,
#    >>> arbolArbitrario(3)
#    Nodo(i=Hoja(x=2), d=Nodo(i=Hoja(x=5), d=Hoja(x=2)))
#    >>> arbolArbitrario(3)
#    Nodo(i=Nodo(i=Hoja(x=6), d=Hoja(x=9)), d=Hoja(x=1))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return Hoja(randint(1, 10 * n))
    k = min(randint(1, n), n - 1)
    return Nodo(arbolArbitrario(k), arbolArbitrario(n - k))

# La propiedad es
@given(st.integers(min_value=1, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mismaForma(n1: int, n2: int) -> None:
    a1 = arbolArbitrario(n1)
    a2 = arbolArbitrario(n2)
    assert mismaForma1(a1, a2) == mismaForma2(a1, a2)

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

from dataclasses import dataclass

from random import randint

from typing import Callable, Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar("A")

B = TypeVar("B")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class Hoja(Arbol[A]):

x: A

@dataclass

class Nodo(Arbol[A]):

i: Arbol[A]

d: Arbol[A]

# -- 1ª solución

# -- ===========

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

match (a, b):

case (Hoja(_), Hoja(_)):

return True

case (Nodo(i1, d1), Nodo(i2, d2)):

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

case (_, _):

return False

assert False

# -- 2ª solución

# -- ===========

# mapArbol(f, t) es el árbolo obtenido aplicando la función f a

# los elementos del árbol t. Por ejemplo,

# >>> mapArbol(lambda x: 1 + x, Nodo(Hoja(2), Hoja(4)))

# Nodo(i=Hoja(x=3), d=Hoja(x=5))

def mapArbol(f: Callable[[A], B], a: Arbol[A]) -> Arbol[B]:

match a:

case Hoja(x):

return Hoja(f(x))

case Nodo(i, d):

return Nodo(mapArbol(f, i), mapArbol(f, d))

assert False

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

return mapArbol(lambda x: 0, a) == mapArbol(lambda x: 0, b)

# Comprobación de equivalencia

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

# arbolArbitrario(n) es un árbol aleatorio de altura n. Por ejemplo,

# >>> arbolArbitrario(3)

# Nodo(i=Hoja(x=2), d=Nodo(i=Hoja(x=5), d=Hoja(x=2)))

# >>> arbolArbitrario(3)

# Nodo(i=Nodo(i=Hoja(x=6), d=Hoja(x=9)), d=Hoja(x=1))

def arbolArbitrario(n: int) -> Arbol[int]:

if n <= 1:

return Hoja(randint(1, 10 * n))

k = min(randint(1, n), n - 1)

return Nodo(arbolArbitrario(k), arbolArbitrario(n - k))

# La propiedad es

@given(st.integers(min_value=1, max_value=10),

st.integers(min_value=1, max_value=10))

def test_mismaForma(n1: int, n2: int) -> None:

a1 = arbolArbitrario(n1)

a2 = arbolArbitrario(n2)

assert mismaForma1(a1, a2) == mismaForma2(a1, a2)

# La comprobación es

# src> poetry run pytest -q arboles_con_la_misma_forma.py

# 1 passed in 0.22s

Día: 8-diciembre-2022

Árboles con la misma forma

Entradas recientes

Buscar

Correo electrónico