diciembre 2022 – Exercitium

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

Profundidad de un árbol binario

PorJosé A. Alonso 16-diciembre-202215-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

   profundidad :: Arbol a -> Int

1	profundidad :: Arbol a -> Int

tal que 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 (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

Comprobar con QuickCheck que para todo árbol biario x, se tiene que

   nNodos x <= 2^(profundidad x) - 1

1	nNodos x <= 2^(profundidad x) - 1

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)

profundidad :: Arbol a -> Int
profundidad (H _)     = 0
profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)

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

-- (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_nNodosProfundidad :: Arbol Int -> Bool
prop_nNodosProfundidad x =
   nNodos x <= 2 ^ profundidad x - 1

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

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

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

profundidad :: Arbol a -> Int

profundidad (H _) = 0

profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)

-- Comprobación de equivalencia

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

-- (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_nNodosProfundidad :: Arbol Int -> Bool

prop_nNodosProfundidad x =

nNodos x <= 2 ^ profundidad x - 1

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

-- La comprobación es

-- λ> quickCheck prop_nNodosProfundidad

-- 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 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 equivalencia
# ============================

# (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

# La propiedad es
@given(st.integers(min_value=1, max_value=10))
def test_nHojas(n: int) -> None:
    a = arbolArbitrario(n)
    assert nNodos(a) <= 2 ** profundidad(a) - 1

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

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

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

# (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

# La propiedad es

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

def test_nHojas(n: int) -> None:

a = arbolArbitrario(n)

assert nNodos(a) <= 2 ** profundidad(a) - 1

# La comprobación es

# src> poetry run pytest -q profundidad_de_un_arbol_binario.py

# 1 passed in 0.11s

Número de hojas de un árbol binario

PorJosé A. Alonso 15-diciembre-202214-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)

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

Definir las funciones

   nHojas :: Arbol a -> Int
   nNodos :: Arbol a -> Int

1 2	nHojas :: Arbol a -> Int nNodos :: Arbol a -> Int

tales que

(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

1	nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3

(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

1	nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2

Comprobar con QuickCheck que en todo árbol binario el número de sus hojas es igual al número de sus nodos más uno.

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)

nHojas :: Arbol a -> Int
nHojas (H _)     = 1
nHojas (N _ i d) = nHojas i + nHojas d

nNodos :: Arbol a -> Int
nNodos (H _)     = 0
nNodos (N _ i d) = 1 + nNodos i + nNodos d

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

-- (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_nHojas :: Arbol Int -> Bool
prop_nHojas x =
  nHojas x == nNodos x + 1

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

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

nHojas :: Arbol a -> Int

nHojas (H _) = 1

nHojas (N _ i d) = nHojas i + nHojas d

nNodos :: Arbol a -> Int

nNodos (H _) = 0

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

-- Comprobación de equivalencia

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

-- (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_nHojas :: Arbol Int -> Bool

prop_nHojas x =

nHojas x == nNodos x + 1

-- La comprobación es

-- λ> quickCheck prop_nHojas

-- 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 nHojas(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 1
        case N(_, i, d):
            return nHojas(i) + nHojas(d)
    assert False

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

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

# (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))])

# La propiedad es
@given(st.integers(min_value=1, max_value=10))
def test_nHojas(n: int) -> None:
    a = arbolArbitrario(n)
    assert nHojas(a) == nNodos(a) + 1

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

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 nHojas(a: Arbol[A]) -> int:

match a:

case H(_):

return 1

case N(_, i, d):

return nHojas(i) + nHojas(d)

assert False

def nNodos(a: Arbol[A]) -> int:

match a:

case H(_):

return 0

case N(_, i, d):

return 1 + nNodos(i) + nNodos(d)

assert False

# Comprobación de equivalencia

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

# (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))])

# La propiedad es

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

def test_nHojas(n: int) -> None:

a = arbolArbitrario(n)

assert nHojas(a) == nNodos(a) + 1

# La comprobación es

# src> poetry run pytest -q numero_de_hojas_de_un_arbol_binario.py

# 1 passed in 0.10s

El tipo de los árboles binarios

PorJosé A. Alonso 15-diciembre-202222-abril-2023

1. El tipo de los árboles binarios en Haskell

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)

usando el tipo de los árboles binarios definido como se muestra a continuación.

import Test.QuickCheck

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

-- Generador de árboles binarios
-- =============================

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

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

-- Generador de árboles binarios

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

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

2. El tipo de los árboles binarios en Python

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

usando la definición de los árboles binarios que se muestra a continuación.

from dataclasses import dataclass
from random import choice, randint
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 nHojas(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 1
        case N(_, i, d):
            return nHojas(i) + nHojas(d)
    assert False

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

# Generador de árboles
# ====================

# (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))])

from dataclasses import dataclass

from random import choice, randint

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 nHojas(a: Arbol[A]) -> int:

match a:

case H(_):

return 1

case N(_, i, d):

return nHojas(i) + nHojas(d)

assert False

def nNodos(a: Arbol[A]) -> int:

match a:

case H(_):

return 0

case N(_, i, d):

return 1 + nNodos(i) + nNodos(d)

assert False

# Generador de árboles

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

# (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))])

El tipo de las expresiones aritméticas: Número de operaciones en una expresión

PorJosé A. Alonso 14-diciembre-202220-abril-2023

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

   numeroOps :: Expr -> Int

1	numeroOps :: Expr -> Int

tal que numeroOps e es el número de operaciones de e. Por ejemplo,

   numeroOps (Lit 3)                      ==  0
   numeroOps (Suma (Lit 7) (Op (Lit 5)))  ==  2

1 2	numeroOps (Lit 3) == 0 numeroOps (Suma (Lit 7) (Op (Lit 5))) == 2

Soluciones

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

Soluciones en Haskell

import Tipo_expresion_aritmetica (Expr (..))

numeroOps :: Expr -> Int
numeroOps (Lit _)        = 0
numeroOps (Suma x y)     = 1 + numeroOps x + numeroOps y
numeroOps (Op x)         = 1 + numeroOps x
numeroOps (SiCero x y z) = 1 + numeroOps x + numeroOps y + numeroOps z

import Tipo_expresion_aritmetica (Expr (..))

numeroOps :: Expr -> Int

numeroOps (Lit _) = 0

numeroOps (Suma x y) = 1 + numeroOps x + numeroOps y

numeroOps (Op x) = 1 + numeroOps x

numeroOps (SiCero x y z) = 1 + numeroOps x + numeroOps y + numeroOps z

Soluciones en Python

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma


def numeroOps(e: Expr) -> int:
    match e:
        case Lit(_):
            return 0
        case Suma(x, y):
            return 1 + numeroOps(x) + numeroOps(y)
        case Op(x):
            return 1 + numeroOps(x)
        case SiCero(x, y, z):
            return 1 + numeroOps(x) + numeroOps(y) + numeroOps(z)
    assert False

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma

def numeroOps(e: Expr) -> int:

match e:

case Lit(_):

return 0

case Suma(x, y):

return 1 + numeroOps(x) + numeroOps(y)

case Op(x):

return 1 + numeroOps(x)

case SiCero(x, y, z):

return 1 + numeroOps(x) + numeroOps(y) + numeroOps(z)

assert False

El tipo de las expresiones aritméticas: Valor de la resta

PorJosé A. Alonso 13-diciembre-202220-abril-2023

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

   resta :: Expr -> Expr -> Expr

1	resta :: Expr -> Expr -> Expr

tal que resta e1 e2 es la expresión correspondiente a la diferencia de e1 y e2. Por ejemplo,

   resta (Lit 42) (Lit 2)  ==  Suma (Lit 42) (Op (Lit 2))

1	resta (Lit 42) (Lit 2) == Suma (Lit 42) (Op (Lit 2))

Comprobar con QuickCheck que

   valor (resta x y) == valor x - valor y

1	valor (resta x y) == valor x - valor y

Soluciones

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

Soluciones en Haskell

import Tipo_expresion_aritmetica (Expr (..))
import Valor_de_una_expresion_aritmetica (valor)
import Test.QuickCheck

resta :: Expr -> Expr -> Expr
resta x y = Suma x (Op y)

-- Comprobación de la propiedad
-- ============================

-- (exprArbitraria n) es una expresión aleatoria de tamaño n. Por
-- ejemplo,
--    λ> sample (exprArbitraria 3)
--    Op (Op (Lit 0))
--    SiCero (Lit 0) (Lit (-2)) (Lit (-1))
--    Op (Suma (Lit 3) (Lit 0))
--    Op (Lit 5)
--    Op (Lit (-1))
--    Op (Op (Lit 9))
--    Suma (Lit (-12)) (Lit (-12))
--    Suma (Lit (-9)) (Lit 10)
--    Op (Suma (Lit 8) (Lit 15))
--    SiCero (Lit 16) (Lit 9) (Lit (-5))
--    Suma (Lit (-3)) (Lit 1)
exprArbitraria :: Int -> Gen Expr
exprArbitraria n
  | n <= 1 = Lit <$> arbitrary
  | otherwise = oneof
                [ Lit <$> arbitrary
                , let m = div n 2
                  in Suma <$> exprArbitraria m <*> exprArbitraria m
                , Op <$> exprArbitraria (n - 1)
                , let m = div n 3
                  in SiCero <$> exprArbitraria m
                            <*> exprArbitraria m
                            <*> exprArbitraria m ]

-- Expr es subclase de Arbitrary
instance Arbitrary Expr where
  arbitrary = sized exprArbitraria


-- La propiedad es
prop_resta :: Expr -> Expr -> Property
prop_resta x y =
  valor (resta x y) === valor x - valor y

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

import Tipo_expresion_aritmetica (Expr (..))

import Valor_de_una_expresion_aritmetica (valor)

import Test.QuickCheck

resta :: Expr -> Expr -> Expr

resta x y = Suma x (Op y)

-- Comprobación de la propiedad

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

-- (exprArbitraria n) es una expresión aleatoria de tamaño n. Por

-- ejemplo,

-- λ> sample (exprArbitraria 3)

-- Op (Op (Lit 0))

-- SiCero (Lit 0) (Lit (-2)) (Lit (-1))

-- Op (Suma (Lit 3) (Lit 0))

-- Op (Lit 5)

-- Op (Lit (-1))

-- Op (Op (Lit 9))

-- Suma (Lit (-12)) (Lit (-12))

-- Suma (Lit (-9)) (Lit 10)

-- Op (Suma (Lit 8) (Lit 15))

-- SiCero (Lit 16) (Lit 9) (Lit (-5))

-- Suma (Lit (-3)) (Lit 1)

exprArbitraria :: Int -> Gen Expr

exprArbitraria n

| n <= 1 = Lit <$> arbitrary

| otherwise = oneof

[ Lit <$> arbitrary

, let m = div n 2

in Suma <$> exprArbitraria m <*> exprArbitraria m

, Op <$> exprArbitraria (n - 1)

, let m = div n 3

in SiCero <$> exprArbitraria m

<*> exprArbitraria m

<*> exprArbitraria m ]

-- Expr es subclase de Arbitrary

instance Arbitrary Expr where

arbitrary = sized exprArbitraria

-- La propiedad es

prop_resta :: Expr -> Expr -> Property

prop_resta x y =

valor (resta x y) === valor x - valor y

-- La comprobación es

-- λ> quickCheck prop_resta

-- +++ OK, passed 100 tests.

Soluciones en Python

from random import choice, randint

from hypothesis import given
from hypothesis import strategies as st

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma
from src.valor_de_una_expresion_aritmetica import valor


def resta(x: Expr, y: Expr) -> Expr:
    return Suma(x, Op(y))

# Comprobación de la propiedad
# ============================

# exprArbitraria(n) es una expresión aleatoria de tamaño n. Por
# ejemplo,
#    >>> exprArbitraria(3)
#    Op(x=Op(x=Lit(x=9)))
#    >>> exprArbitraria(3)
#    Op(x=SiCero(x=Lit(x=6), y=Lit(x=2), z=Lit(x=6)))
#    >>> exprArbitraria(3)
#    Suma(x=Lit(x=8), y=Lit(x=2))
def exprArbitraria(n: int) -> Expr:
    if n <= 1:
        return Lit(randint(0, 10))
    m = n // 2
    return choice([Lit(randint(0, 10)),
                   Suma(exprArbitraria(m), exprArbitraria(m)),
                   Op(exprArbitraria(n - 1)),
                   SiCero(exprArbitraria(m),
                          exprArbitraria(m),
                          exprArbitraria(m))])

# 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:
    x = exprArbitraria(n1)
    y = exprArbitraria(n2)
    assert valor(resta(x, y)) == valor(x) - valor(y)

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

from random import choice, randint

from hypothesis import given

from hypothesis import strategies as st

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma

from src.valor_de_una_expresion_aritmetica import valor

def resta(x: Expr, y: Expr) -> Expr:

return Suma(x, Op(y))

# Comprobación de la propiedad

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

# exprArbitraria(n) es una expresión aleatoria de tamaño n. Por

# ejemplo,

# >>> exprArbitraria(3)

# Op(x=Op(x=Lit(x=9)))

# >>> exprArbitraria(3)

# Op(x=SiCero(x=Lit(x=6), y=Lit(x=2), z=Lit(x=6)))

# >>> exprArbitraria(3)

# Suma(x=Lit(x=8), y=Lit(x=2))

def exprArbitraria(n: int) -> Expr:

if n <= 1:

return Lit(randint(0, 10))

m = n // 2

return choice([Lit(randint(0, 10)),

Suma(exprArbitraria(m), exprArbitraria(m)),

Op(exprArbitraria(n - 1)),

SiCero(exprArbitraria(m),

exprArbitraria(m),

exprArbitraria(m))])

# 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:

x = exprArbitraria(n1)

y = exprArbitraria(n2)

assert valor(resta(x, y)) == valor(x) - valor(y)

# La comprobación es

# src> poetry run pytest -q valor_de_la_resta.py

# 1 passed in 0.21s

El tipo de las expresiones aritméticas: Valor de una expresión

PorJosé A. Alonso 12-diciembre-202220-abril-2023

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

   valor :: Expr -> Int

1	valor :: Expr -> Int

tal que valor e es el valor de la expresión e (donde el valor de SiCero e e1 e2 es el valor de e1 si el valor de e es cero y el es el valor de e2, en caso contrario). Por ejemplo,

   valor (Op (Suma (Lit 3) (Lit 5)))      ==  -8
   valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4
   valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5

valor (Op (Suma (Lit 3) (Lit 5))) == -8

valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4

valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5

Soluciones

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

Soluciones en Haskell

import Tipo_expresion_aritmetica (Expr (..))

valor :: Expr -> Int
valor (Lit n)        = n
valor (Suma x y)     = valor x + valor y
valor (Op x)         = - valor x
valor (SiCero x y z) | valor x == 0 = valor y
                     | otherwise    = valor z

import Tipo_expresion_aritmetica (Expr (..))

valor :: Expr -> Int

valor (Lit n) = n

valor (Suma x y) = valor x + valor y

valor (Op x) = - valor x

valor (SiCero x y z) | valor x == 0 = valor y

| otherwise = valor z

Soluciones en Python

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma

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

def valor(e: Expr) -> int:
    match e:
        case Lit(n):
            return n
        case Suma(x, y):
            return valor(x) + valor(y)
        case Op(x):
            return -valor(x)
        case SiCero(x, y, z):
            return valor(y) if valor(x) == 0 else valor(z)
    assert False

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

def valor2(e: Expr) -> int:
    if isinstance(e, Lit):
        return e.x
    if isinstance(e, Suma):
        return valor2(e.x) + valor2(e.y)
    if isinstance(e, Op):
        return -valor2(e.x)
    if isinstance(e, SiCero):
        if valor2(e.x) == 0:
            return valor2(e.y)
        return valor2(e.z)
    assert False

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma

# 1ª solución

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

def valor(e: Expr) -> int:

match e:

case Lit(n):

return n

case Suma(x, y):

return valor(x) + valor(y)

case Op(x):

return -valor(x)

case SiCero(x, y, z):

return valor(y) if valor(x) == 0 else valor(z)

assert False

# 2ª solución

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

def valor2(e: Expr) -> int:

if isinstance(e, Lit):

return e.x

if isinstance(e, Suma):

return valor2(e.x) + valor2(e.y)

if isinstance(e, Op):

return -valor2(e.x)

if isinstance(e, SiCero):

if valor2(e.x) == 0:

return valor2(e.y)

return valor2(e.z)

assert False

El tipo de las expresiones aritméticas

PorJosé A. Alonso 12-diciembre-202220-abril-2023

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

El tipo de las expresiones aritméticas formadas por

literales (p.e. Lit 7),
sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

se define como se muestra a continuación.

data Expr = Lit Int
          | Suma Expr Expr
          | Op Expr
          | SiCero Expr Expr Expr
  deriving (Eq, Show)

data Expr = Lit Int

| Suma Expr Expr

| Op Expr

| SiCero Expr Expr Expr

deriving (Eq, Show)

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

El tipo de las expresiones aritméticas formadas por

literales (p.e. Lit 7),
sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

se define como se muestra a continuación.

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class Lit(Expr):
    x: int

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

@dataclass
class Op(Expr):
    x: Expr

@dataclass
class SiCero(Expr):
    x: Expr
    y: Expr
    z: Expr

from dataclasses import dataclass

@dataclass

class Expr:

pass

@dataclass

class Lit(Expr):

x: int

@dataclass

class Suma(Expr):

x: Expr

y: Expr

@dataclass

class Op(Expr):

x: Expr

@dataclass

class SiCero(Expr):

x: Expr

y: Expr

z: Expr

Árbol con las hojas en la profundidad dada

PorJosé A. Alonso 9-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

   creaArbol :: Int -> Arbol ()

1	creaArbol :: Int -> Arbol ()

tal que creaArbol n es el árbol cuyas hoyas están en la profundidad n. Por ejemplo,

   λ> creaArbol 2
   Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ()))

1 2	λ> creaArbol 2 Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ()))

Soluciones

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

Soluciones en Haskell

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

creaArbol :: Int -> Arbol ()
creaArbol h
  | h <= 0    = Hoja ()
  | otherwise = Nodo x x
  where x = creaArbol (h - 1)

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

deriving (Show, Eq)

creaArbol :: Int -> Arbol ()

creaArbol h

| h <= 0 = Hoja ()

| otherwise = Nodo x x

where x = creaArbol (h - 1)

Soluciones en Python

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

A = TypeVar("A")

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

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

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

def creaArbol(h: int) -> Arbol[Any]:
    if h <= 0:
        return Hoja(None)
    x = creaArbol(h - 1)
    return Nodo(x, x)

from dataclasses import dataclass

from typing import Any, Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class Hoja(Arbol[A]):

x: A

@dataclass

class Nodo(Arbol[A]):

i: Arbol[A]

d: Arbol[A]

def creaArbol(h: int) -> Arbol[Any]:

if h <= 0:

return Hoja(None)

x = creaArbol(h - 1)

return Nodo(x, x)

Á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

Aplicación de una función a un árbol

PorJosé A. Alonso 7-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

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

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

tal que mapArbol f t es el árbolo 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)

1 2	λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4)) Nodo (Hoja 3) (Hoja 5)

Soluciones

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

Soluciones en Haskell

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

mapArbol :: (a -> b) -> Arbol a -> Arbol b
mapArbol f (Hoja a)   = Hoja (f a)
mapArbol f (Nodo l r) = Nodo (mapArbol f l) (mapArbol f r)

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

deriving (Show, Eq)

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

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

mapArbol f (Nodo l r) = Nodo (mapArbol f l) (mapArbol f r)

Soluciones en Python

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

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]

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

from dataclasses import dataclass

from typing import Callable, Generic, TypeVar

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]

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

Altura de un árbol binario

PorJosé A. Alonso 6-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)

Definir la función

   altura :: Arbol a -> Int

1	altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

λ> altura (Hoja 1)

λ> altura (Nodo (Hoja 1) (Hoja 6))

λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))

λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))

Soluciones

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

Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)

altura :: Arbol a -> Int
altura (Hoja _)   = 0
altura (Nodo i d) = 1 + max (altura i) (altura d)

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

altura :: Arbol a -> Int

altura (Hoja _) = 0

altura (Nodo i d) = 1 + max (altura i) (altura d)

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

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

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

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

def altura(a: Arbol[A]) -> int:
    match a:
        case Hoja(_):
            return 0
        case Nodo(i, d):
            return 1 + max(altura(i), altura(d))
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class Hoja(Arbol[A]):

x: A

@dataclass

class Nodo(Arbol[A]):

i: Arbol[A]

d: Arbol[A]

def altura(a: Arbol[A]) -> int:

match a:

case Hoja(_):

return 0

case Nodo(i, d):

return 1 + max(altura(i), altura(d))

assert False

El tipo de los árboles binarios con valores en las hojas

PorJosé A. Alonso 6-diciembre-202223-abril-2023

1. El tipo de los árboles binarios con valores en las hojas en Haskell

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

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

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

-- (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]

data Arbol a = Hoja a

| Nodo (Arbol a) (Arbol a)

deriving (Eq, Show)

-- (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]

2. El tipo de los árboles binarios con valores en las hojas en Python

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

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

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

A = TypeVar("A")

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

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

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

# Generador
# =========

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

from dataclasses import dataclass

from typing import Generic, TypeVar

from random import randint

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class Hoja(Arbol[A]):

x: A

@dataclass

class Nodo(Arbol[A]):

i: Arbol[A]

d: Arbol[A]

# Generador

# =========

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

# >>> arbolArbitrario(2)

# Nodo(i=Nodo(i=Hoja(x=6), d=Hoja(x=3)), d=Nodo(i=Hoja(x=4), d=Hoja(x=4)))

# >>> arbolArbitrario(2)

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

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

if n == 0:

return Hoja(randint(1, 10))

if n == 1:

return Nodo(arbolArbitrario(0), arbolArbitrario(0))

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

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

El tipo de las fórmulas proposicionales: Reconocedor de tautologías

PorJosé A. Alonso 5-diciembre-202215-abril-2023

Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,

(A ∧ B) → A es una tautología
A → (A ∧ B) no es una tautología

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   esTautologia :: FProp -> Bool

1	esTautologia :: FProp -> Bool

tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,

   λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
   True
   λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   False

λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))

True

λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))

False

Soluciones

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

Soluciones en Haskell

import Tipo_de_formulas (FProp(..))
import Valor_de_una_formula (valor)
import Interpretaciones_de_una_formula (interpretaciones)

esTautologia :: FProp -> Bool
esTautologia p =
  and [valor i p | i <- interpretaciones p]

import Tipo_de_formulas (FProp(..))

import Valor_de_una_formula (valor)

import Interpretaciones_de_una_formula (interpretaciones)

esTautologia :: FProp -> Bool

esTautologia p =

and [valor i p | i <- interpretaciones p]

Soluciones en Python

from src.interpretaciones_de_una_formula import interpretaciones
from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var
from src.valor_de_una_formula import valor

def esTautologia(p: FProp) -> bool:
    return all((valor(i, p) for i in interpretaciones(p)))

from src.interpretaciones_de_una_formula import interpretaciones

from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var

from src.valor_de_una_formula import valor

def esTautologia(p: FProp) -> bool:

return all((valor(i, p) for i in interpretaciones(p)))

El tipo de las fórmulas proposicionales: Interpretaciones de una fórmula

PorJosé A. Alonso 2-diciembre-202215-abril-2023

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   interpretaciones :: FProp -> [Interpretacion]

1	interpretaciones :: FProp -> [Interpretacion]

tal que interpretaciones p es la lista de las interpretaciones de la fórmula p. Por ejemplo,

   λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   [[('A',False),('B',False)],
    [('A',False),('B',True)],
    [('A',True),('B',False)],
    [('A',True),('B',True)]]

λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))

[[('A',False),('B',False)],

[('A',False),('B',True)],

[('A',True),('B',False)],

[('A',True),('B',True)]]

Soluciones

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

Soluciones en Haskell

import Tipo_de_formulas (FProp(..))
import Variables_de_una_formula (variables)
import Valor_de_una_formula (Interpretacion)
import Data.List (nub)

interpretaciones :: FProp -> [Interpretacion]
interpretaciones p =
  [zip vs i | i <- interpretacionesVar (length vs)]
  where vs = nub (variables p)

-- (interpretacionesVar n) es la lista de las interpretaciones de n
-- variables. Por ejemplo,
--    λ> interpretacionesVar 2
--    [[False,False],
--     [False,True],
--     [True,False],
--     [True,True]]
interpretacionesVar :: Int -> [[Bool]]
interpretacionesVar 0 = [[]]
interpretacionesVar n = map (False:) bss ++ map (True:) bss
  where bss = interpretacionesVar (n-1)

import Tipo_de_formulas (FProp(..))

import Variables_de_una_formula (variables)

import Valor_de_una_formula (Interpretacion)

import Data.List (nub)

interpretaciones :: FProp -> [Interpretacion]

interpretaciones p =

[zip vs i | i <- interpretacionesVar (length vs)]

where vs = nub (variables p)

-- (interpretacionesVar n) es la lista de las interpretaciones de n

-- variables. Por ejemplo,

-- λ> interpretacionesVar 2

-- [[False,False],

-- [False,True],

-- [True,False],

-- [True,True]]

interpretacionesVar :: Int -> [[Bool]]

interpretacionesVar 0 = [[]]

interpretacionesVar n = map (False:) bss ++ map (True:) bss

where bss = interpretacionesVar (n-1)

Soluciones en Python

from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var
from src.valor_de_una_formula import Interpretacion
from src.variables_de_una_formula import variables

# interpretacionesVar(n) es la lista de las interpretaciones de n
# variables. Por ejemplo,
#    >>> interpretacionesVar 2
#    [[False, False],
#     [False, True],
#     [True, False],
#     [True, True]]
def interpretacionesVar(n: int) -> list[list[bool]]:
    if n == 0:
        return [[]]
    bss = interpretacionesVar(n-1)
    return [[False] + x for x in bss] + [[True] + x for x in bss]

def interpretaciones(f: FProp) -> list[Interpretacion]:
    vs = list(set(variables(f)))
    return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]

from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var

from src.valor_de_una_formula import Interpretacion

from src.variables_de_una_formula import variables

# interpretacionesVar(n) es la lista de las interpretaciones de n

# variables. Por ejemplo,

# >>> interpretacionesVar 2

# [[False, False],

# [False, True],

# [True, False],

# [True, True]]

def interpretacionesVar(n: int) -> list[list[bool]]:

if n == 0:

return [[]]

bss = interpretacionesVar(n-1)

return [[False] + x for x in bss] + [[True] + x for x in bss]

def interpretaciones(f: FProp) -> list[Interpretacion]:

vs = list(set(variables(f)))

return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]

El tipo de las fórmulas proposicionales: Valor de una fórmula

PorJosé A. Alonso 1-diciembre-202215-abril-2023

Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por

   [('A', True), ('B', False)]

1	[('A', True), ('B', False)]

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

1	type Interpretacion = [(Char, Bool)]

El valor de una fórmula en una interpretación se calcula usando las funciones de verdad de las conectivas que se muestran a continuación

   |---+----|   |---+---+-------+-------|
   | p | ¬p |   | p | q | p ∧ q | p → q |
   |---+----|   |---+---+-------+-------|
   | T | F  |   | T | T | T     | T     |
   | F | T  |   | T | F | F     | F     |
   |---+----|   | F | T | F     | T     |
                | F | F | F     | T     |
                |---+---+-------+-------|

|---+----| |---+---+-------+-------|

| p | ¬p | | p | q | p ∧ q | p → q |

|---+----| |---+---+-------+-------|

| T | F | | T | T | T | T |

| F | T | | T | F | F | F |

|---+----| | F | T | F | T |

| F | F | F | T |

|---+---+-------+-------|

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   valor :: Interpretacion -> FProp -> Bool

1	valor :: Interpretacion -> FProp -> Bool

tal que valor i p es el valor de la fórmula p en la interpretación i. Por ejemplo,

   λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
   λ> valor [('A',False),('B',False)] p
   True
   λ> valor [('A',True),('B',False)] p
   False

λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))

λ> valor [('A',False),('B',False)] p

True

λ> valor [('A',True),('B',False)] p

False

Soluciones

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

Soluciones en Haskell

import Tipo_de_formulas (FProp(..))

type Interpretacion = [(Char, Bool)]

valor :: Interpretacion -> FProp -> Bool
valor _ (Const b)  = b
valor i (Var x)    = busca x i
valor i (Neg p)    = not (valor i p)
valor i (Conj p q) = valor i p && valor i q
valor i (Impl p q) = valor i p <= valor i q

-- (busca c t) es el valor del primer elemento de la lista de asociación
-- t cuya clave es c. Por ejemplo,
--    busca 2 [(1,'a'),(3,'d'),(2,'c')]  ==  'c'
busca :: Eq c => c -> [(c,v)] -> v
busca c t = head [v | (c',v) <- t, c == c']

import Tipo_de_formulas (FProp(..))

type Interpretacion = [(Char, Bool)]

valor :: Interpretacion -> FProp -> Bool

valor _ (Const b) = b

valor i (Var x) = busca x i

valor i (Neg p) = not (valor i p)

valor i (Conj p q) = valor i p && valor i q

valor i (Impl p q) = valor i p <= valor i q

-- (busca c t) es el valor del primer elemento de la lista de asociación

-- t cuya clave es c. Por ejemplo,

-- busca 2 [(1,'a'),(3,'d'),(2,'c')] == 'c'

busca :: Eq c => c -> [(c,v)] -> v

busca c t = head [v | (c',v) <- t, c == c']

Soluciones en Python

from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var

Interpretacion = list[tuple[str, bool]]

# busca(c, t) es el valor del primer elemento de la lista de asociación
# t cuya clave es c. Por ejemplo,
#    >>> busca('B', [('A', True), ('B', False), ('C', True)])
#    False
def busca(c: str, i: Interpretacion) -> bool:
    return [v for (d, v) in i if d == c][0]

def valor(i: Interpretacion, f: FProp) -> bool:
    match f:
        case Const(b):
            return b
        case Var(x):
            return busca(x, i)
        case Neg(p):
            return not valor(i, p)
        case Conj(p, q):
            return valor(i, p) and valor(i, q)
        case Impl(p, q):
            return valor(i, p) <= valor(i, q)
    assert False

from src.tipo_de_formulas import Conj, Const, FProp, Impl, Neg, Var

Interpretacion = list[tuple[str, bool]]

# busca(c, t) es el valor del primer elemento de la lista de asociación

# t cuya clave es c. Por ejemplo,

# >>> busca('B', [('A', True), ('B', False), ('C', True)])

# False

def busca(c: str, i: Interpretacion) -> bool:

return [v for (d, v) in i if d == c][0]

def valor(i: Interpretacion, f: FProp) -> bool:

match f:

case Const(b):

return b

case Var(x):

return busca(x, i)

case Neg(p):

return not valor(i, p)

case Conj(p, q):

return valor(i, p) and valor(i, q)

case Impl(p, q):

return valor(i, p) <= valor(i, q)

assert False

Meses: diciembre 2022

Existencia de elementos del árbol que verifican una propiedad

Árboles con igual estructura

Árboles con bordes iguales

Árboles balanceados

Rama izquierda de un árbol binario

Suma de un árbol

El tipo de los árboles binarios con valores en los nodos

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

Árbol de profundidad n con nodos iguales

Subárbol de profundidad dada

Imagen especular de un árbol binario

Recorrido de árboles binarios

Profundidad de un árbol binario

Número de hojas de un árbol binario

El tipo de los árboles binarios

1. El tipo de los árboles binarios en Haskell

2. El tipo de los árboles binarios en Python

El tipo de las expresiones aritméticas: Número de operaciones en una expresión

El tipo de las expresiones aritméticas: Valor de la resta

El tipo de las expresiones aritméticas: Valor de una expresión

El tipo de las expresiones aritméticas

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

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

Árbol con las hojas en la profundidad dada

Árboles con la misma forma

Aplicación de una función a un árbol

Altura de un árbol binario

El tipo de los árboles binarios con valores en las hojas

1. El tipo de los árboles binarios con valores en las hojas en Haskell

2. El tipo de los árboles binarios con valores en las hojas en Python

El tipo de las fórmulas proposicionales: Reconocedor de tautologías

El tipo de las fórmulas proposicionales: Interpretaciones de una fórmula

El tipo de las fórmulas proposicionales: Valor de una fórmula

Entradas recientes

Buscar

Correo electrónico