Exercitium

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

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

PorJosé A. Alonso 30-noviembre-202215-abril-2023

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

   variables :: FProp -> [Char]

1	variables :: FProp -> [Char]

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

   λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
   "AB"
   λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
   "AAB"

λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))

"AB"

λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))

"AAB"

Soluciones

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

Soluciones en Haskell

import Tipo_de_formulas (FProp(..))

variables :: FProp -> [Char]
variables (Const _)  = []
variables (Var x)    = [x]
variables (Neg p)    = variables p
variables (Conj p q) = variables p ++ variables q
variables (Impl p q) = variables p ++ variables q

import Tipo_de_formulas (FProp(..))

variables :: FProp -> [Char]

variables (Const _) = []

variables (Var x) = [x]

variables (Neg p) = variables p

variables (Conj p q) = variables p ++ variables q

variables (Impl p q) = variables p ++ variables q

Soluciones en Python

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

def variables(f: FProp) -> list[str]:
    match f:
        case Const(_):
            return []
        case Var(x):
            return [x]
        case Neg(p):
            return variables(p)
        case Conj(p, q):
            return variables(p) + variables(q)
        case Impl(p, q):
            return variables(p) + variables(q)
    assert False

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

def variables(f: FProp) -> list[str]:

match f:

case Const(_):

return []

case Var(x):

return [x]

case Neg(p):

return variables(p)

case Conj(p, q):

return variables(p) + variables(q)

case Impl(p, q):

return variables(p) + variables(q)

assert False

El tipo de las fórmulas proposicionales

PorJosé A. Alonso 30-noviembre-202215-abril-2023

1. El tipo de las fórmulas proposicionales en Haskell

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

1	Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

usando el tipo de las fórmulas proposicionales definido por

data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show

data FProp = Const Bool

| Var Char

| Neg FProp

| Conj FProp FProp

| Impl FProp FProp

deriving Show

1. El tipo de las fórmulas proposicionales en Haskell

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl(Var('A'), Conj(Const(False), Neg (Var('B'))))

1	Impl(Var('A'), Conj(Const(False), Neg (Var('B'))))

usando el tipo de las fórmulas proposicionales definido por

from dataclasses import dataclass


@dataclass
class FProp:
    pass

@dataclass
class Const(FProp):
    x: bool

@dataclass
class Var(FProp):
    x: str

@dataclass
class Neg(FProp):
    x: FProp

@dataclass
class Conj(FProp):
    x: FProp
    y: FProp

@dataclass
class Impl(FProp):
    x: FProp
    y: FProp

from dataclasses import dataclass

@dataclass

class FProp:

pass

@dataclass

class Const(FProp):

x: bool

@dataclass

class Var(FProp):

x: str

@dataclass

class Neg(FProp):

x: FProp

@dataclass

class Conj(FProp):

x: FProp

y: FProp

@dataclass

class Impl(FProp):

x: FProp

y: FProp

El tipo de los árboles binarios

PorJosé A. Alonso 29-noviembre-202214-diciembre-2022

El árbol binario

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

/ \

3 7

/ \ / \

1 4 6 9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
                  5
                  (Nodo (Hoja 6) 7 (Hoja 9))

ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))

(Nodo (Hoja 6) 7 (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol = Hoja Int
              | Nodo Arbol Int Arbol

1 2	data Arbol = Hoja Int \| Nodo Arbol Int Arbol

Definir las funciones

   ocurre :: Int -> Arbol -> Bool
   aplana :: Arbol -> [Int]

1 2	ocurre :: Int -> Arbol -> Bool aplana :: Arbol -> [Int]

tales que

ocurre m a se verifica si m ocurre en el árbol a. Por ejemplo,

     ocurre 4  ejArbol  ==  True
     ocurre 10 ejArbol  ==  False

1 2	ocurre 4 ejArbol == True ocurre 10 ejArbol == False

aplana a es la lista obtenida aplanando el árbol a. Por ejemplo,

     aplana ejArbol  ==  [1,3,4,5,6,7,9]

1	aplana ejArbol == [1,3,4,5,6,7,9]

Soluciones

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

Soluciones en Haskell

data Arbol = Hoja Int
           | Nodo Arbol Int Arbol

ejArbol :: Arbol
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
               5
               (Nodo (Hoja 6) 7 (Hoja 9))

ocurre :: Int -> Arbol -> Bool
ocurre m (Hoja n)     = m == n
ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d

aplana :: Arbol -> [Int]
aplana (Hoja n)     = [n]
aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d

data Arbol = Hoja Int

| Nodo Arbol Int Arbol

ejArbol :: Arbol

ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))

(Nodo (Hoja 6) 7 (Hoja 9))

ocurre :: Int -> Arbol -> Bool

ocurre m (Hoja n) = m == n

ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d

aplana :: Arbol -> [Int]

aplana (Hoja n) = [n]

aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d

Soluciones en Python

from dataclasses import dataclass

@dataclass
class Arbol:
    pass

@dataclass
class Hoja(Arbol):
    x: int

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

ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)),
               5,
               Nodo(Hoja(6), 7, Hoja(9)))

def ocurre(m: int, a: Arbol) -> bool:
    match a:
        case Hoja(n):
            return m == n
        case Nodo(i, n, d):
            return m == n or ocurre(m, i) or ocurre(m, d)
    assert False

def aplana(a: Arbol) -> list[int]:
    match a:
        case Hoja(n):
            return [n]
        case Nodo(i, n, d):
            return aplana(i) + [n] + aplana(d)
    assert False

from dataclasses import dataclass

@dataclass

class Arbol:

pass

@dataclass

class Hoja(Arbol):

x: int

@dataclass

class Nodo(Arbol):

i: Arbol

x: int

d: Arbol

ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)),

Nodo(Hoja(6), 7, Hoja(9)))

def ocurre(m: int, a: Arbol) -> bool:

match a:

case Hoja(n):

return m == n

case Nodo(i, n, d):

return m == n or ocurre(m, i) or ocurre(m, d)

assert False

def aplana(a: Arbol) -> list[int]:

match a:

case Hoja(n):

return [n]

case Nodo(i, n, d):

return aplana(i) + [n] + aplana(d)

assert False

El tipo de las listas

PorJosé A. Alonso 28-noviembre-202214-diciembre-2022

El tipo de las listas, con elementos de tipo a, se puede definir por

   data Lista a = Nil | Cons a (Lista a)

1	data Lista a = Nil \| Cons a (Lista a)

Por ejemplo, la lista [4,2,5] se representa por Cons 4 (Cons 2 (Cons 5 Nil)).

Definir la función

   longitud :: Lista a -> Int

1	longitud :: Lista a -> Int

tal que longitud xs es la longitud de la lista xs. Por ejemplo,

   longitud (Cons 4 (Cons 2 (Cons 5 Nil)))  ==  3

1	longitud (Cons 4 (Cons 2 (Cons 5 Nil))) == 3

Soluciones

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

Soluciones en Haskell

data Lista a = Nil | Cons a (Lista a)

longitud :: Lista a -> Int
longitud Nil         = 0
longitud (Cons _ xs) = 1 + longitud xs

data Lista a = Nil | Cons a (Lista a)

longitud :: Lista a -> Int

longitud Nil = 0

longitud (Cons _ xs) = 1 + longitud xs

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

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

@dataclass
class Nil(Lista[A]):
    pass

@dataclass
class Cons(Lista[A]):
    x: A
    xs: Lista[A]

def longitud(xs: Lista[A]) -> int:
    match xs:
        case Nil():
            return 0
        case Cons(_, xs):
            return 1 + longitud(xs)
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Lista(Generic[A]):

pass

@dataclass

class Nil(Lista[A]):

pass

@dataclass

class Cons(Lista[A]):

x: A

xs: Lista[A]

def longitud(xs: Lista[A]) -> int:

match xs:

case Nil():

return 0

case Cons(_, xs):

return 1 + longitud(xs)

assert False

El tipo de los números naturales

PorJosé A. Alonso 25-noviembre-202214-diciembre-2022

El tipo de los números raturales se puede definir por

   data Nat = Cero | Suc Nat
     deriving (Show, Eq)

1 2	data Nat = Cero \| Suc Nat deriving (Show, Eq)

de forma que Suc (Suc (Suc Cero)) representa el número 3.

Definir las siguientes funciones

   nat2int :: Nat -> Int
   int2nat :: Int -> Nat
   suma    :: Nat -> Nat -> Nat

nat2int :: Nat -> Int

int2nat :: Int -> Nat

suma :: Nat -> Nat -> Nat

tales que

nat2int n es el número entero correspondiente al número natural n. Por ejemplo,

     nat2int (Suc (Suc (Suc Cero)))  ==  3

1	nat2int (Suc (Suc (Suc Cero))) == 3

int2nat n es el número natural correspondiente al número entero n. Por ejemplo,

     int2nat 3  ==  Suc (Suc (Suc Cero))

1	int2nat 3 == Suc (Suc (Suc Cero))

suma m n es la suma de los número naturales m y n. Por ejemplo,

     λ> suma (Suc (Suc Cero)) (Suc Cero)
     Suc (Suc (Suc Cero))
     λ> nat2int (suma (Suc (Suc Cero)) (Suc Cero))
     3
     λ> nat2int (suma (int2nat 2) (int2nat 1))
     3

λ> suma (Suc (Suc Cero)) (Suc Cero)

Suc (Suc (Suc Cero))

λ> nat2int (suma (Suc (Suc Cero)) (Suc Cero))

λ> nat2int (suma (int2nat 2) (int2nat 1))

Soluciones

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

Soluciones en Haskell

data Nat = Cero | Suc Nat
  deriving (Show, Eq)

nat2int :: Nat -> Int
nat2int Cero    = 0
nat2int (Suc n) = 1 + nat2int n

int2nat :: Int -> Nat
int2nat 0 = Cero
int2nat n = Suc (int2nat (n-1))

suma :: Nat -> Nat -> Nat
suma Cero    n = n
suma (Suc m) n = Suc (suma m n)

data Nat = Cero | Suc Nat

deriving (Show, Eq)

nat2int :: Nat -> Int

nat2int Cero = 0

nat2int (Suc n) = 1 + nat2int n

int2nat :: Int -> Nat

int2nat 0 = Cero

int2nat n = Suc (int2nat (n-1))

suma :: Nat -> Nat -> Nat

suma Cero n = n

suma (Suc m) n = Suc (suma m n)

Soluciones en Python

from dataclasses import dataclass

@dataclass
class Nat:
    pass

@dataclass
class Cero(Nat):
    pass

@dataclass
class Suc(Nat):
    n: Nat

def nat2int(n: Nat) -> int:
    match n:
        case Cero():
            return 0
        case Suc(n):
            return 1 + nat2int(n)
    assert False

def int2nat(n: int) -> Nat:
    if n == 0:
        return Cero()
    return Suc(int2nat(n - 1))

def suma(m: Nat, n: Nat) -> Nat:
    match m:
        case Cero():
            return n
        case Suc(m):
            return Suc(suma(m, n))
    assert False

from dataclasses import dataclass

@dataclass

class Nat:

pass

@dataclass

class Cero(Nat):

pass

@dataclass

class Suc(Nat):

n: Nat

def nat2int(n: Nat) -> int:

match n:

case Cero():

return 0

case Suc(n):

return 1 + nat2int(n)

assert False

def int2nat(n: int) -> Nat:

if n == 0:

return Cero()

return Suc(int2nat(n - 1))

def suma(m: Nat, n: Nat) -> Nat:

match m:

case Cero():

return n

case Suc(m):

return Suc(suma(m, n))

assert False

El tipo de figuras geométricas

PorJosé A. Alonso 24-noviembre-202214-diciembre-2022

Se consideran las figuras geométricas formadas por circulos (definidos por su radio) y rectángulos (definidos por su base y su altura). El tipo de las figura geométricas se define por

   data Figura = Circulo Float | Rect Float Float

1	data Figura = Circulo Float \| Rect Float Float

Definir las funciones

   area     :: Figura -> Float
   cuadrado :: Float -> Figura

1 2	area :: Figura -> Float cuadrado :: Float -> Figura

tales que

area f es el área de la figura f. Por ejemplo,

     area (Circulo 1)   ==  3.1415927
     area (Circulo 2)   ==  12.566371
     area (Rect 2 5)    ==  10.0

area (Circulo 1) == 3.1415927

area (Circulo 2) == 12.566371

area (Rect 2 5) == 10.0

cuadrado n es el cuadrado de lado n. Por ejemplo,

     area (cuadrado 3)  ==  9.0

1	area (cuadrado 3) == 9.0

Soluciones

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

Soluciones en Haskell

data Figura = Circulo Float | Rect Float Float

area :: Figura -> Float
area (Circulo r) = pi*r^2
area (Rect x y)  = x*y

cuadrado :: Float -> Figura
cuadrado n = Rect n n

data Figura = Circulo Float | Rect Float Float

area :: Figura -> Float

area (Circulo r) = pi*r^2

area (Rect x y) = x*y

cuadrado :: Float -> Figura

cuadrado n = Rect n n

Soluciones en Python

from dataclasses import dataclass
from math import pi

@dataclass
class Figura:
    """Figuras geométricas"""

@dataclass
class Circulo(Figura):
    r: float

@dataclass
class Rect(Figura):
    x: float
    y: float

def area(f: Figura) -> float:
    match f:
        case Circulo(r):
            return pi * r**2
        case Rect(x, y):
            return x * y
    assert False

def cuadrado(n: float) -> Figura:
    return Rect(n, n)

from dataclasses import dataclass

from math import pi

@dataclass

class Figura:

"""Figuras geométricas"""

@dataclass

class Circulo(Figura):

r: float

@dataclass

class Rect(Figura):

x: float

y: float

def area(f: Figura) -> float:

match f:

case Circulo(r):

return pi * r**2

case Rect(x, y):

return x * y

assert False

def cuadrado(n: float) -> Figura:

return Rect(n, n)

Movimientos en el plano

PorJosé A. Alonso 23-noviembre-202214-diciembre-2022

Se consideran el tipo de las posiciones del plano definido por

   type Posicion = (Int,Int)
   <7p
y el tipo de las direcciones definido por
<pre lang="text">
   data Direccion = Izquierda | Derecha | Arriba | Abajo
     deriving Show

type Posicion = (Int,Int)

<7p

y el tipo de las direcciones definido por

data Direccion = Izquierda | Derecha | Arriba | Abajo

deriving Show

Definir las siguientes funciones

   opuesta     :: Direccion -> Direccion
   movimiento  :: Posicion -> Direccion -> Posicion
   movimientos :: Posicion -> [Direccion] -> Posicion

opuesta :: Direccion -> Direccion

movimiento :: Posicion -> Direccion -> Posicion

movimientos :: Posicion -> [Direccion] -> Posicion

tales que

opuesta d es la dirección opuesta de d. Por ejemplo,

     opuesta Izquierda == Derecha

1	opuesta Izquierda == Derecha

movimiento p d es la posición reultante de moverse, desde la posición p, un paso en la dirección d. Por ejemplo,

     movimiento (2,5) Arriba          == (2,6)
     movimiento (2,5) (opuesta Abajo) == (2,6)

1 2	movimiento (2,5) Arriba == (2,6) movimiento (2,5) (opuesta Abajo) == (2,6)

movimientos p ds es la posición obtenida aplicando la lista de movimientos según las direcciones de ds a la posición p. Por ejemplo,

     movimientos (2,5)  [Arriba, Izquierda] == (1,6)

1	movimientos (2,5) [Arriba, Izquierda] == (1,6)

Soluciones

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

Soluciones en Haskell

type Posicion = (Int,Int)

data Direccion = Izquierda | Derecha | Arriba | Abajo
  deriving Show

-- Definición de opuesta
-- =====================

opuesta :: Direccion -> Direccion
opuesta Izquierda = Derecha
opuesta Derecha   = Izquierda
opuesta Arriba    = Abajo
opuesta Abajo     = Arriba

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

movimiento1 :: Posicion -> Direccion -> Posicion
movimiento1 (x,y) Izquierda = (x-1,y)
movimiento1 (x,y) Derecha   = (x+1,y)
movimiento1 (x,y) Arriba    = (x,y+1)
movimiento1 (x,y) Abajo     = (x,y-1)

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

movimiento2 :: Posicion -> Direccion -> Posicion
movimiento2 (x,y) d =
  case d of
    Izquierda -> (x-1,y)
    Derecha   -> (x+1,y)
    Arriba    -> (x,y+1)
    Abajo     -> (x,y-1)

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

movimientos1 :: Posicion -> [Direccion] -> Posicion
movimientos1 p []     = p
movimientos1 p (d:ds) = movimientos1 (movimiento1 p d) ds

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

movimientos2 :: Posicion -> [Direccion] -> Posicion
movimientos2 = foldl movimiento1

type Posicion = (Int,Int)

data Direccion = Izquierda | Derecha | Arriba | Abajo

deriving Show

-- Definición de opuesta

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

opuesta :: Direccion -> Direccion

opuesta Izquierda = Derecha

opuesta Derecha = Izquierda

opuesta Arriba = Abajo

opuesta Abajo = Arriba

-- 1ª definición de movimiento

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

movimiento1 :: Posicion -> Direccion -> Posicion

movimiento1 (x,y) Izquierda = (x-1,y)

movimiento1 (x,y) Derecha = (x+1,y)

movimiento1 (x,y) Arriba = (x,y+1)

movimiento1 (x,y) Abajo = (x,y-1)

-- 2ª definición de movimiento

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

movimiento2 :: Posicion -> Direccion -> Posicion

movimiento2 (x,y) d =

case d of

Izquierda -> (x-1,y)

Derecha -> (x+1,y)

Arriba -> (x,y+1)

Abajo -> (x,y-1)

-- 1ª definición de movimientos

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

movimientos1 :: Posicion -> [Direccion] -> Posicion

movimientos1 p [] = p

movimientos1 p (d:ds) = movimientos1 (movimiento1 p d) ds

-- 2ª definición de movimientos

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

movimientos2 :: Posicion -> [Direccion] -> Posicion

movimientos2 = foldl movimiento1

Soluciones en Python

from enum import Enum
from functools import reduce

Posicion = tuple[int, int]

Direccion = Enum('Direccion', ['Izquierda', 'Derecha', 'Arriba', 'Abajo'])

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

def opuesta1(d: Direccion) -> Direccion:
    if d == Direccion.Izquierda:
        return Direccion.Derecha
    if d == Direccion.Derecha:
        return Direccion.Izquierda
    if d == Direccion.Arriba:
        return Direccion.Abajo
    if d == Direccion.Abajo:
        return Direccion.Arriba
    assert False

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

def opuesta2(d: Direccion) -> Direccion:
    match d:
        case Direccion.Izquierda:
            return Direccion.Derecha
        case Direccion.Derecha:
            return Direccion.Izquierda
        case Direccion.Arriba:
            return Direccion.Abajo
        case Direccion.Abajo:
            return Direccion.Arriba
    assert False

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

def movimiento1(p: Posicion, d: Direccion) -> Posicion:
    (x, y) = p
    if d == Direccion.Izquierda:
        return (x - 1, y)
    if d == Direccion.Derecha:
        return (x + 1, y)
    if d == Direccion.Arriba:
        return (x, y + 1)
    if d == Direccion.Abajo:
        return (x, y - 1)
    assert False

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

def movimiento2(p: Posicion, d: Direccion) -> Posicion:
    (x, y) = p
    match d:
        case Direccion.Izquierda:
            return (x - 1, y)
        case Direccion.Derecha:
            return (x + 1, y)
        case Direccion.Arriba:
            return (x, y + 1)
        case Direccion.Abajo:
            return (x, y - 1)
    assert False

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

def movimientos1(p: Posicion, ds: list[Direccion]) -> Posicion:
    if not ds:
        return p
    return movimientos1(movimiento1(p, ds[0]), ds[1:])

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

def movimientos2(p: Posicion, ds: list[Direccion]) -> Posicion:
    return reduce(movimiento1, ds, p)

from enum import Enum

from functools import reduce

Posicion = tuple[int, int]

Direccion = Enum('Direccion', ['Izquierda', 'Derecha', 'Arriba', 'Abajo'])

# 1ª definición de opuesta

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

def opuesta1(d: Direccion) -> Direccion:

if d == Direccion.Izquierda:

return Direccion.Derecha

if d == Direccion.Derecha:

return Direccion.Izquierda

if d == Direccion.Arriba:

return Direccion.Abajo

if d == Direccion.Abajo:

return Direccion.Arriba

assert False

# 2ª definición de opuesta

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

def opuesta2(d: Direccion) -> Direccion:

match d:

case Direccion.Izquierda:

return Direccion.Derecha

case Direccion.Derecha:

return Direccion.Izquierda

case Direccion.Arriba:

return Direccion.Abajo

case Direccion.Abajo:

return Direccion.Arriba

assert False

# 1ª definición de movimiento

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

def movimiento1(p: Posicion, d: Direccion) -> Posicion:

(x, y) = p

if d == Direccion.Izquierda:

return (x - 1, y)

if d == Direccion.Derecha:

return (x + 1, y)

if d == Direccion.Arriba:

return (x, y + 1)

if d == Direccion.Abajo:

return (x, y - 1)

assert False

# 2ª definición de movimiento

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

def movimiento2(p: Posicion, d: Direccion) -> Posicion:

(x, y) = p

match d:

case Direccion.Izquierda:

return (x - 1, y)

case Direccion.Derecha:

return (x + 1, y)

case Direccion.Arriba:

return (x, y + 1)

case Direccion.Abajo:

return (x, y - 1)

assert False

# 1ª definición de movimientos

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

def movimientos1(p: Posicion, ds: list[Direccion]) -> Posicion:

if not ds:

return p

return movimientos1(movimiento1(p, ds[0]), ds[1:])

# 2ª definición de movimientos

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

def movimientos2(p: Posicion, ds: list[Direccion]) -> Posicion:

return reduce(movimiento1, ds, p)

Máximo de una lista

PorJosé A. Alonso 22-noviembre-20222-enero-2023

Definir la función

   maximo :: Ord a => [a] -> a

1	maximo :: Ord a => [a] -> a

tal que maximo xs es el máximo de la lista xs. Por ejemplo,

   maximo [3,7,2,5]                  ==  7
   maximo ["todo","es","falso"]      ==  "todo"
   maximo ["menos","alguna","cosa"]  ==  "menos"

maximo [3,7,2,5] == 7

maximo ["todo","es","falso"] == "todo"

maximo ["menos","alguna","cosa"] == "menos"

Soluciones

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

Soluciones en Haskell

import Data.List (foldl1')
import Test.QuickCheck

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

maximo1 :: Ord a => [a] -> a
maximo1 [x]      = x
maximo1 (x:y:ys) = max x (maximo1 (y:ys))

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

maximo2 :: Ord a => [a] -> a
maximo2 = foldr1 max

-- 3ª solución
-- ===========

maximo3 :: Ord a => [a] -> a
maximo3 = foldl1' max

-- 4ª solución
-- ===========

maximo4 :: Ord a => [a] -> a
maximo4 = maximum

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

-- La propiedad es
prop_maximo :: NonEmptyList Int -> Bool
prop_maximo (NonEmpty xs) =
  all (== maximo1 xs)
      [maximo2 xs,
       maximo3 xs]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> maximo1 [0..5*10^6]
--    5000000
--    (3.42 secs, 1,783,406,728 bytes)
--    λ> maximo2 [0..5*10^6]
--    5000000
--    (0.80 secs, 934,638,080 bytes)
--    λ> maximo3 [0..5*10^6]
--    5000000
--    (0.12 secs, 360,591,360 bytes)
--    λ> maximo4 [0..5*10^6]
--    5000000
--    (1.40 secs, 892,891,608 bytes)

import Data.List (foldl1')

import Test.QuickCheck

-- 1ª solución

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

maximo1 :: Ord a => [a] -> a

maximo1 [x] = x

maximo1 (x:y:ys) = max x (maximo1 (y:ys))

-- 2ª solución

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

maximo2 :: Ord a => [a] -> a

maximo2 = foldr1 max

-- 3ª solución

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

maximo3 :: Ord a => [a] -> a

maximo3 = foldl1' max

-- 4ª solución

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

maximo4 :: Ord a => [a] -> a

maximo4 = maximum

-- Comprobación de equivalencia

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

-- La propiedad es

prop_maximo :: NonEmptyList Int -> Bool

prop_maximo (NonEmpty xs) =

all (== maximo1 xs)

[maximo2 xs,

maximo3 xs]

-- La comprobación es

-- λ> quickCheck prop_maximo

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> maximo1 [0..5*10^6]

-- 5000000

-- (3.42 secs, 1,783,406,728 bytes)

-- λ> maximo2 [0..5*10^6]

-- 5000000

-- (0.80 secs, 934,638,080 bytes)

-- λ> maximo3 [0..5*10^6]

-- 5000000

-- (0.12 secs, 360,591,360 bytes)

-- λ> maximo4 [0..5*10^6]

-- 5000000

-- (1.40 secs, 892,891,608 bytes)

Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar, Union

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A', bound=Union[int, float, str])

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

def maximo1(xs: list[A]) -> A:
    if len(xs) == 1:
        return xs[0]
    return max(xs[0], maximo1(xs[1:]))

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

def maximo2(xs: list[A]) -> A:
    return reduce(max, xs)

# 3ª solución
# ===========

def maximo3(xs: list[A]) -> A:
    return max(xs)

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

# La propiedad es
@given(st.lists(st.integers(), min_size=2))
def test_maximo(xs: list[int]) -> None:
    r = maximo1(xs)
    assert maximo2(xs) == r
    assert maximo3(xs) == r

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

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('maximo1(range(2*10**4))')
#    0.03 segundos
#    >>> tiempo('maximo2(range(2*10**4))')
#    0.00 segundos
#    >>> tiempo('maximo3(range(2*10**4))')
#    0.00 segundos
#
#    >>> tiempo('maximo2(range(5*10**6))')
#    0.38 segundos
#    >>> tiempo('maximo3(range(5*10**6))')
#    0.21 segundos

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar, Union

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A', bound=Union[int, float, str])

# 1ª solución

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

def maximo1(xs: list[A]) -> A:

if len(xs) == 1:

return xs[0]

return max(xs[0], maximo1(xs[1:]))

# 2ª solución

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

def maximo2(xs: list[A]) -> A:

return reduce(max, xs)

# 3ª solución

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

def maximo3(xs: list[A]) -> A:

return max(xs)

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers(), min_size=2))

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

r = maximo1(xs)

assert maximo2(xs) == r

assert maximo3(xs) == r

# La comprobación es

# src> poetry run pytest -q maximo_de_una_lista.py

# 1 passed in 0.33s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('maximo1(range(2*10**4))')

# 0.03 segundos

# >>> tiempo('maximo2(range(2*10**4))')

# 0.00 segundos

# >>> tiempo('maximo3(range(2*10**4))')

# 0.00 segundos

# >>> tiempo('maximo2(range(5*10**6))')

# 0.38 segundos

# >>> tiempo('maximo3(range(5*10**6))')

# 0.21 segundos

Aplica según propiedad

PorJosé A. Alonso 21-noviembre-202214-abril-2023

Definir la función

   filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b]

1	filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b]

tal que filtraAplica f p xs es la lista obtenida aplicándole a los elementos de xs que cumplen el predicado p la función f. Por ejemplo,

   filtraAplica (4+) (<3) [1..7]  ==  [5,6]

1	filtraAplica (4+) (<3) [1..7] == [5,6]

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck.HigherOrder (quickCheck')

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

filtraAplica1 :: (a -> b) -> (a -> Bool) -> [a] -> [b]
filtraAplica1 f p xs = [f x | x <- xs, p x]

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

filtraAplica2 :: (a -> b) -> (a -> Bool) -> [a] -> [b]
filtraAplica2 f p xs = map f (filter p xs)

-- 3ª solución
-- ===========

filtraAplica3 :: (a -> b) -> (a -> Bool) -> [a] -> [b]
filtraAplica3 _ _ [] = []
filtraAplica3 f p (x:xs) | p x       = f x : filtraAplica3 f p xs
                         | otherwise = filtraAplica3 f p xs

-- 4ª solución
-- ===========

filtraAplica4 :: (a -> b) -> (a -> Bool) -> [a] -> [b]
filtraAplica4 f p = foldr g []
  where g x y | p x       = f x : y
              | otherwise = y

-- 5ª solución
-- ===========

filtraAplica5 :: (a -> b) -> (a -> Bool) -> [a] -> [b]
filtraAplica5 f p =
  foldr (\x y -> if p x then f x : y else y) []

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

-- La propiedad es
prop_filtraAplica :: (Int -> Int) -> (Int -> Bool) -> [Int] -> Bool
prop_filtraAplica f p xs =
  all (== filtraAplica1 f p xs)
      [filtraAplica2 f p xs,
       filtraAplica3 f p xs,
       filtraAplica4 f p xs,
       filtraAplica5 f p xs]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> sum (filtraAplica1 id even [1..5*10^6])
--    6250002500000
--    (2.92 secs, 1,644,678,696 bytes)
--    λ> sum (filtraAplica2 id even [1..5*10^6])
--    6250002500000
--    (1.17 secs, 1,463,662,848 bytes)
--    λ> sum (filtraAplica3 id even [1..5*10^6])
--    6250002500000
--    (3.18 secs, 1,964,678,640 bytes)
--    λ> sum (filtraAplica4 id even [1..5*10^6])
--    6250002500000
--    (2.64 secs, 1,924,678,752 bytes)
--    λ> sum (filtraAplica5 id even [1..5*10^6])
--    6250002500000
--    (2.61 secs, 1,824,678,712 bytes)

import Test.QuickCheck.HigherOrder (quickCheck')

-- 1ª solución

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

filtraAplica1 :: (a -> b) -> (a -> Bool) -> [a] -> [b]

filtraAplica1 f p xs = [f x | x <- xs, p x]

-- 2ª solución

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

filtraAplica2 :: (a -> b) -> (a -> Bool) -> [a] -> [b]

filtraAplica2 f p xs = map f (filter p xs)

-- 3ª solución

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

filtraAplica3 :: (a -> b) -> (a -> Bool) -> [a] -> [b]

filtraAplica3 _ _ [] = []

filtraAplica3 f p (x:xs) | p x = f x : filtraAplica3 f p xs

| otherwise = filtraAplica3 f p xs

-- 4ª solución

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

filtraAplica4 :: (a -> b) -> (a -> Bool) -> [a] -> [b]

filtraAplica4 f p = foldr g []

where g x y | p x = f x : y

| otherwise = y

-- 5ª solución

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

filtraAplica5 :: (a -> b) -> (a -> Bool) -> [a] -> [b]

filtraAplica5 f p =

foldr (\x y -> if p x then f x : y else y) []

-- Comprobación de equivalencia

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

-- La propiedad es

prop_filtraAplica :: (Int -> Int) -> (Int -> Bool) -> [Int] -> Bool

prop_filtraAplica f p xs =

all (== filtraAplica1 f p xs)

[filtraAplica2 f p xs,

filtraAplica3 f p xs,

filtraAplica4 f p xs,

filtraAplica5 f p xs]

-- La comprobación es

-- λ> quickCheck' prop_filtraAplica

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> sum (filtraAplica1 id even [1..5*10^6])

-- 6250002500000

-- (2.92 secs, 1,644,678,696 bytes)

-- λ> sum (filtraAplica2 id even [1..5*10^6])

-- 6250002500000

-- (1.17 secs, 1,463,662,848 bytes)

-- λ> sum (filtraAplica3 id even [1..5*10^6])

-- 6250002500000

-- (3.18 secs, 1,964,678,640 bytes)

-- λ> sum (filtraAplica4 id even [1..5*10^6])

-- 6250002500000

-- (2.64 secs, 1,924,678,752 bytes)

-- λ> sum (filtraAplica5 id even [1..5*10^6])

-- 6250002500000

-- (2.61 secs, 1,824,678,712 bytes)

Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Callable, TypeVar

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')
B = TypeVar('B')

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

def filtraAplica1(f: Callable[[A], B],
                  p: Callable[[A], bool],
                  xs: list[A]) -> list[B]:
    return [f(x) for x in xs if p(x)]

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

def filtraAplica2(f: Callable[[A], B],
                  p: Callable[[A], bool],
                  xs: list[A]) -> list[B]:
    return list(map(f, filter(p, xs)))

# 3ª solución
# ===========

def filtraAplica3(f: Callable[[A], B],
                  p: Callable[[A], bool],
                  xs: list[A]) -> list[B]:
    if not xs:
        return []
    if p(xs[0]):
        return [f(xs[0])] + filtraAplica3(f, p, xs[1:])
    return filtraAplica3(f, p, xs[1:])

# 4ª solución
# ===========

def filtraAplica4(f: Callable[[A], B],
                  p: Callable[[A], bool],
                  xs: list[A]) -> list[B]:
    def g(ys: list[B], x: A) -> list[B]:
        if p(x):
            return ys + [f(x)]
        return ys

    return reduce(g, xs, [])

# 5ª solución
# ===========

def filtraAplica5(f: Callable[[A], B],
                  p: Callable[[A], bool],
                  xs: list[A]) -> list[B]:
    r = []
    for x in xs:
        if p(x):
            r.append(f(x))
    return r

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

# La propiedad es
@given(st.lists(st.integers()))
def test_filtraAplica(xs: list[int]) -> None:
    def f(x: int) -> int:
        return x + 4
    def p(x: int) -> bool:
        return x < 3
    r = filtraAplica1(f, p, xs)
    assert filtraAplica2(f, p, xs) == r
    assert filtraAplica3(f, p, xs) == r
    assert filtraAplica4(f, p, xs) == r
    assert filtraAplica5(f, p, xs) == r

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

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**5))')
#    0.02 segundos
#    >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**5))')
#    0.01 segundos
#    >>> tiempo('filtraAplica3(lambda x: x, lambda x: x % 2 == 0, range(10**5))')
#    Process Python violación de segmento (core dumped)
#    >>> tiempo('filtraAplica4(lambda x: x, lambda x: x % 2 == 0, range(10**5))')
#    4.07 segundos
#    >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**5))')
#    0.01 segundos
#
#    >>> tiempo('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**7))')
#    1.66 segundos
#    >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**7))')
#    1.00 segundos
#    >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**7))')
#    1.21 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Callable, TypeVar

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

B = TypeVar('B')

# 1ª solución

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

def filtraAplica1(f: Callable[[A], B],

p: Callable[[A], bool],

xs: list[A]) -> list[B]:

return [f(x) for x in xs if p(x)]

# 2ª solución

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

def filtraAplica2(f: Callable[[A], B],

p: Callable[[A], bool],

xs: list[A]) -> list[B]:

return list(map(f, filter(p, xs)))

# 3ª solución

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

def filtraAplica3(f: Callable[[A], B],

p: Callable[[A], bool],

xs: list[A]) -> list[B]:

if not xs:

return []

if p(xs[0]):

return [f(xs[0])] + filtraAplica3(f, p, xs[1:])

return filtraAplica3(f, p, xs[1:])

# 4ª solución

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

def filtraAplica4(f: Callable[[A], B],

p: Callable[[A], bool],

xs: list[A]) -> list[B]:

def g(ys: list[B], x: A) -> list[B]:

if p(x):

return ys + [f(x)]

return ys

return reduce(g, xs, [])

# 5ª solución

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

def filtraAplica5(f: Callable[[A], B],

p: Callable[[A], bool],

xs: list[A]) -> list[B]:

r = []

for x in xs:

if p(x):

r.append(f(x))

return r

# Comprobación de equivalencia

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

# La propiedad es

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

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

def f(x: int) -> int:

return x + 4

def p(x: int) -> bool:

return x < 3

r = filtraAplica1(f, p, xs)

assert filtraAplica2(f, p, xs) == r

assert filtraAplica3(f, p, xs) == r

assert filtraAplica4(f, p, xs) == r

assert filtraAplica5(f, p, xs) == r

# La comprobación es

# src> poetry run pytest -q aplica_segun_propiedad.py

# 1 passed in 0.25s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**5))')

# 0.02 segundos

# >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**5))')

# 0.01 segundos

# >>> tiempo('filtraAplica3(lambda x: x, lambda x: x % 2 == 0, range(10**5))')

# Process Python violación de segmento (core dumped)

# >>> tiempo('filtraAplica4(lambda x: x, lambda x: x % 2 == 0, range(10**5))')

# 4.07 segundos

# >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**5))')

# 0.01 segundos

# >>> tiempo('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**7))')

# 1.66 segundos

# >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**7))')

# 1.00 segundos

# >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**7))')

# 1.21 segundos

Concatenación de una lista de listas

PorJosé A. Alonso 18-noviembre-202214-diciembre-2022

Definir, por recursión, la función

   conc :: [[a]] -> [a]

1	conc :: [[a]] -> [a]

tal que conc xss es la concenación de las listas de xss. Por ejemplo,

   conc [[1,3],[2,4,6],[1,9]]  ==  [1,3,2,4,6,1,9]

1	conc [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9]

Comprobar con QuickCheck que la longitud de conc xss es la suma de las longitudes de los elementos de xss.

Soluciones

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

Soluciones en Haskell

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

conc1 :: [[a]] -> [a]
conc1 xss = [x | xs <- xss, x <- xs]

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

conc2 :: [[a]] -> [a]
conc2 []       = []
conc2 (xs:xss) = xs ++ conc2 xss

-- 3ª solución
-- ===========

conc3 :: [[a]] -> [a]
conc3 = foldr (++) []

-- 4ª solución
-- ===========

conc4 :: [[a]] -> [a]
conc4 = concat

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

-- La propiedad es
prop_conc :: [[Int]] -> Bool
prop_conc xss =
  all (== conc1 xss)
      [conc2 xss,
       conc3 xss,
       conc4 xss]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (conc1 [[1..n] | n <- [1..5000]])
--    12502500
--    (2.72 secs, 1,802,391,200 bytes)
--    λ> length (conc2 [[1..n] | n <- [1..5000]])
--    12502500
--    (0.27 secs, 1,602,351,160 bytes)
--    λ> length (conc3 [[1..n] | n <- [1..5000]])
--    12502500
--    (0.28 secs, 1,602,071,192 bytes)
--    λ> length (conc4 [[1..n] | n <- [1..5000]])
--    12502500
--    (0.26 secs, 1,602,071,184 bytes)

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

-- La propiedad es
prop_long_conc :: [[Int]] -> Bool
prop_long_conc xss =
  length (conc1 xss) == sum (map length xss)

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

-- 1ª solución

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

conc1 :: [[a]] -> [a]

conc1 xss = [x | xs <- xss, x <- xs]

-- 2ª solución

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

conc2 :: [[a]] -> [a]

conc2 [] = []

conc2 (xs:xss) = xs ++ conc2 xss

-- 3ª solución

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

conc3 :: [[a]] -> [a]

conc3 = foldr (++) []

-- 4ª solución

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

conc4 :: [[a]] -> [a]

conc4 = concat

-- Comprobación de equivalencia

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

-- La propiedad es

prop_conc :: [[Int]] -> Bool

prop_conc xss =

all (== conc1 xss)

[conc2 xss,

conc3 xss,

conc4 xss]

-- La comprobación es

-- λ> quickCheck prop_conc

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (conc1 [[1..n] | n <- [1..5000]])

-- 12502500

-- (2.72 secs, 1,802,391,200 bytes)

-- λ> length (conc2 [[1..n] | n <- [1..5000]])

-- 12502500

-- (0.27 secs, 1,602,351,160 bytes)

-- λ> length (conc3 [[1..n] | n <- [1..5000]])

-- 12502500

-- (0.28 secs, 1,602,071,192 bytes)

-- λ> length (conc4 [[1..n] | n <- [1..5000]])

-- 12502500

-- (0.26 secs, 1,602,071,184 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_long_conc :: [[Int]] -> Bool

prop_long_conc xss =

length (conc1 xss) == sum (map length xss)

-- La comprobación es

-- λ> quickCheck prop_long_conc

-- +++ OK, passed 100 tests.

Soluciones en Python

from functools import reduce
from operator import concat
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Any, TypeVar

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

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

def conc1(xss: list[list[A]]) -> list[A]:
    return [x for xs in xss for x in xs]

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

def conc2(xss: list[list[A]]) -> list[A]:
    if not xss:
        return []
    return xss[0] + conc2(xss[1:])

# 3ª solución
# ===========

def conc3(xss: Any) -> Any:
    return reduce(concat, xss)

# 4ª solución
# ===========

def conc4(xss: list[list[A]]) -> list[A]:
    r = []
    for xs in xss:
        for x in xs:
            r.append(x)
    return r

# La propiedad es
@given(st.lists(st.lists(st.integers()), min_size=1))
def test_conc(xss: list[list[int]]) -> None:
    r = conc1(xss)
    assert conc2(xss) == r
    assert conc3(xss) == r
    assert conc4(xss) == r

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

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('conc1([list(range(n)) for n in range(1500)])')
#    0.04 segundos
#    >>> tiempo('conc2([list(range(n)) for n in range(1500)])')
#    6.28 segundos
#    >>> tiempo('conc3([list(range(n)) for n in range(1500)])')
#    2.55 segundos
#    >>> tiempo('conc4([list(range(n)) for n in range(1500)])')
#    0.09 segundos
#
#    >>> tiempo('conc1([list(range(n)) for n in range(10000)])')
#    2.01 segundos
#    >>> tiempo('conc4([list(range(n)) for n in range(10000)])')
#    2.90 segundos
#
# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.lists(st.lists(st.integers()), min_size=1))
def test_long_conc(xss: list[list[int]]) -> None:
    assert len(conc1(xss)) == sum(map(len, xss))

# prop_long_conc :: [[Int]] -> Bool
# prop_long_conc xss =
#   length (conc1 xss) == sum (map length xss)
#
# La comprobación es
#    λ> quickCheck prop_long_conc
#    +++ OK, passed 100 tests.

from functools import reduce

from operator import concat

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Any, TypeVar

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

def conc1(xss: list[list[A]]) -> list[A]:

return [x for xs in xss for x in xs]

# 2ª solución

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

def conc2(xss: list[list[A]]) -> list[A]:

if not xss:

return []

return xss[0] + conc2(xss[1:])

# 3ª solución

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

def conc3(xss: Any) -> Any:

return reduce(concat, xss)

# 4ª solución

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

def conc4(xss: list[list[A]]) -> list[A]:

r = []

for xs in xss:

for x in xs:

r.append(x)

return r

# La propiedad es

@given(st.lists(st.lists(st.integers()), min_size=1))

def test_conc(xss: list[list[int]]) -> None:

r = conc1(xss)

assert conc2(xss) == r

assert conc3(xss) == r

assert conc4(xss) == r

# La comprobación es

# src> poetry run pytest -q contenacion_de_una_lista_de_listas.py

# 1 passed in 0.63s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('conc1([list(range(n)) for n in range(1500)])')

# 0.04 segundos

# >>> tiempo('conc2([list(range(n)) for n in range(1500)])')

# 6.28 segundos

# >>> tiempo('conc3([list(range(n)) for n in range(1500)])')

# 2.55 segundos

# >>> tiempo('conc4([list(range(n)) for n in range(1500)])')

# 0.09 segundos

# >>> tiempo('conc1([list(range(n)) for n in range(10000)])')

# 2.01 segundos

# >>> tiempo('conc4([list(range(n)) for n in range(10000)])')

# 2.90 segundos

# Comprobación de la propiedad

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

# La propiedad es

@given(st.lists(st.lists(st.integers()), min_size=1))

def test_long_conc(xss: list[list[int]]) -> None:

assert len(conc1(xss)) == sum(map(len, xss))

# prop_long_conc :: [[Int]] -> Bool

# prop_long_conc xss =

# length (conc1 xss) == sum (map length xss)

# La comprobación es

# λ> quickCheck prop_long_conc

# +++ OK, passed 100 tests.

Agrupación de elementos por posición

PorJosé A. Alonso 17-noviembre-202214-diciembre-2022

Definir la función

   agrupa :: Eq a => [[a]] -> [[a]]

1	agrupa :: Eq a => [[a]] -> [[a]]

tal que agrupa xsses la lista de las listas obtenidas agrupando los primeros elementos, los segundos, … Por ejemplo,

   agrupa [[1..6],[7..9],[10..20]]  ==  [[1,7,10],[2,8,11],[3,9,12]]

1	agrupa [[1..6],[7..9],[10..20]] == [[1,7,10],[2,8,11],[3,9,12]]

Comprobar con QuickChek que la longitud de todos los elementos de agrupa xs es igual a la longitud de xs.

Soluciones

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

Soluciones en Haskell

import Data.List (transpose)
import qualified Data.Matrix as M (fromLists, toLists, transpose)
import Test.QuickCheck

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

-- (primeros xss) es la lista de los primeros elementos de xss. Por
-- ejemplo,
--    primeros [[1..6],[7..9],[10..20]]  ==  [1,7,10]
primeros :: [[a]] -> [a]
primeros = map head

-- (restos xss) es la lista de los restos de elementos de xss. Por
-- ejemplo,
--    restos [[1..3],[7,8],[4..7]]  ==  [[2,3],[8],[5,6,7]]
restos :: [[a]] -> [[a]]
restos = map tail

agrupa1 :: Eq a => [[a]] -> [[a]]
agrupa1 []  = []
agrupa1 xss
  | [] `elem` xss = []
  | otherwise     = primeros xss : agrupa1 (restos xss)

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

-- (conIgualLongitud xss) es la lista obtenida recortando los elementos
-- de xss para que todos tengan la misma longitud. Por ejemplo,
--    > conIgualLongitud [[1..6],[7..9],[10..20]]
--    [[1,2,3],[7,8,9],[10,11,12]]
conIgualLongitud :: [[a]] -> [[a]]
conIgualLongitud xss = map (take n) xss
  where n = minimum (map length xss)

agrupa2 :: Eq a => [[a]] -> [[a]]
agrupa2 = transpose . conIgualLongitud

-- 3ª solución
-- ===========

agrupa3 :: Eq a => [[a]] -> [[a]]
agrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud

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

-- La propiedad es
prop_agrupa :: NonEmptyList [Int] -> Bool
prop_agrupa (NonEmpty xss) =
  all (== agrupa1 xss)
      [agrupa2 xss,
       agrupa3 xss]

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (agrupa1 [[1..10^4] | _ <- [1..10^4]])
--    10000
--    (3.96 secs, 16,012,109,904 bytes)
--    λ> length (agrupa2 [[1..10^4] | _ <- [1..10^4]])
--    10000
--    (25.80 secs, 19,906,197,528 bytes)
--    λ> length (agrupa3 [[1..10^4] | _ <- [1..10^4]])
--    10000
--    (9.56 secs, 7,213,797,984 bytes)

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

-- La propiedad es
prop_agrupa_length :: [[Int]] -> Bool
prop_agrupa_length xss =
  and [length xs == n | xs <- agrupa1 xss]
  where n = length xss

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

import Data.List (transpose)

import qualified Data.Matrix as M (fromLists, toLists, transpose)

import Test.QuickCheck

-- 1ª solución

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

-- (primeros xss) es la lista de los primeros elementos de xss. Por

-- ejemplo,

-- primeros [[1..6],[7..9],[10..20]] == [1,7,10]

primeros :: [[a]] -> [a]

primeros = map head

-- (restos xss) es la lista de los restos de elementos de xss. Por

-- ejemplo,

-- restos [[1..3],[7,8],[4..7]] == [[2,3],[8],[5,6,7]]

restos :: [[a]] -> [[a]]

restos = map tail

agrupa1 :: Eq a => [[a]] -> [[a]]

agrupa1 [] = []

agrupa1 xss

| [] `elem` xss = []

| otherwise = primeros xss : agrupa1 (restos xss)

-- 2ª solución

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

-- (conIgualLongitud xss) es la lista obtenida recortando los elementos

-- de xss para que todos tengan la misma longitud. Por ejemplo,

-- > conIgualLongitud [[1..6],[7..9],[10..20]]

-- [[1,2,3],[7,8,9],[10,11,12]]

conIgualLongitud :: [[a]] -> [[a]]

conIgualLongitud xss = map (take n) xss

where n = minimum (map length xss)

agrupa2 :: Eq a => [[a]] -> [[a]]

agrupa2 = transpose . conIgualLongitud

-- 3ª solución

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

agrupa3 :: Eq a => [[a]] -> [[a]]

agrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud

-- Comprobación de equivalencia

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

-- La propiedad es

prop_agrupa :: NonEmptyList [Int] -> Bool

prop_agrupa (NonEmpty xss) =

all (== agrupa1 xss)

[agrupa2 xss,

agrupa3 xss]

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (agrupa1 [[1..10^4] | _ <- [1..10^4]])

-- 10000

-- (3.96 secs, 16,012,109,904 bytes)

-- λ> length (agrupa2 [[1..10^4] | _ <- [1..10^4]])

-- 10000

-- (25.80 secs, 19,906,197,528 bytes)

-- λ> length (agrupa3 [[1..10^4] | _ <- [1..10^4]])

-- 10000

-- (9.56 secs, 7,213,797,984 bytes)

-- La comprobación es

-- λ> quickCheck prop_agrupa

-- +++ OK, passed 100 tests.

-- La propiedad es

prop_agrupa_length :: [[Int]] -> Bool

prop_agrupa_length xss =

and [length xs == n | xs <- agrupa1 xss]

where n = length xss

-- La comprobación es

-- λ> quickCheck prop_agrupa_length

-- +++ OK, passed 100 tests.

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st
from numpy import transpose, array

setrecursionlimit(10**6)

A = TypeVar('A')

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

# primeros(xss) es la lista de los primeros elementos de xss. Por
# ejemplo,
#    primeros([[1,6],[7,8,9],[3,4,5]])  ==  [1, 7, 3]
def primeros(xss: list[list[A]]) -> list[A]:
    return [xs[0] for xs in xss]

# restos(xss) es la lista de los restos de elementos de xss. Por
# ejemplo,
#    >>> restos([[1,6],[7,8,9],[3,4,5]])
#    [[6], [8, 9], [4, 5]]
def restos(xss: list[list[A]]) -> list[list[A]]:
    return [xs[1:] for xs in xss]

def agrupa1(xss: list[list[A]]) -> list[list[A]]:
    if not xss:
        return []
    if [] in xss:
        return []
    return [primeros(xss)] + agrupa1(restos(xss))

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

# conIgualLongitud(xss) es la lista obtenida recortando los elementos
# de xss para que todos tengan la misma longitud. Por ejemplo,
#    >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]])
#    [[1, 6], [7, 8], [3, 4]]
def conIgualLongitud(xss: list[list[A]]) -> list[list[A]]:
    n = min(map(len, xss))
    return [xs[:n] for xs in xss]

def agrupa2(xss: list[list[A]]) -> list[list[A]]:
    yss = conIgualLongitud(xss)
    return [[ys[i] for ys in yss] for i in range(len(yss[0]))]

# 3ª solución
# ===========

def agrupa3(xss: list[list[A]]) -> list[list[A]]:
    yss = conIgualLongitud(xss)
    return list(map(list, zip(*yss)))

# 4ª solución
# ===========

def agrupa4(xss: list[list[A]]) -> list[list[A]]:
    yss = conIgualLongitud(xss)
    return (transpose(array(yss))).tolist()

# 5ª solución
# ===========

def agrupa5(xss: list[list[A]]) -> list[list[A]]:
    yss = conIgualLongitud(xss)
    r = []
    for i in range(len(yss[0])):
        f = []
        for xs in xss:
            f.append(xs[i])
        r.append(f)
    return r

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

# La propiedad es
@given(st.lists(st.lists(st.integers()), min_size=1))
def test_agrupa(xss: list[list[int]]) -> None:
    r = agrupa1(xss)
    assert agrupa2(xss) == r
    assert agrupa3(xss) == r
    assert agrupa4(xss) == r
    assert agrupa5(xss) == r

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

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('agrupa1([list(range(10**3)) for _ in range(10**3)])')
#    4.44 segundos
#    >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])')
#    0.10 segundos
#    >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])')
#    0.10 segundos
#    >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])')
#    0.12 segundos
#    >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])')
#    0.15 segundos
#
#    >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])')
#    21.25 segundos
#    >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])')
#    20.82 segundos
#    >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])')
#    13.46 segundos
#    >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])')
#    21.70 segundos

# La propiedad es
@given(st.lists(st.lists(st.integers()), min_size=1))
def test_agrupa_length(xss: list[list[int]]) -> None:
    n = len(xss)
    assert all((len(xs) == n for xs in agrupa2(xss)))

# La comprobación es
#    src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py
#    2 passed in 1.25s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from numpy import transpose, array

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

# primeros(xss) es la lista de los primeros elementos de xss. Por

# ejemplo,

# primeros([[1,6],[7,8,9],[3,4,5]]) == [1, 7, 3]

def primeros(xss: list[list[A]]) -> list[A]:

return [xs[0] for xs in xss]

# restos(xss) es la lista de los restos de elementos de xss. Por

# ejemplo,

# >>> restos([[1,6],[7,8,9],[3,4,5]])

# [[6], [8, 9], [4, 5]]

def restos(xss: list[list[A]]) -> list[list[A]]:

return [xs[1:] for xs in xss]

def agrupa1(xss: list[list[A]]) -> list[list[A]]:

if not xss:

return []

if [] in xss:

return []

return [primeros(xss)] + agrupa1(restos(xss))

# 2ª solución

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

# conIgualLongitud(xss) es la lista obtenida recortando los elementos

# de xss para que todos tengan la misma longitud. Por ejemplo,

# >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]])

# [[1, 6], [7, 8], [3, 4]]

def conIgualLongitud(xss: list[list[A]]) -> list[list[A]]:

n = min(map(len, xss))

return [xs[:n] for xs in xss]

def agrupa2(xss: list[list[A]]) -> list[list[A]]:

yss = conIgualLongitud(xss)

return [[ys[i] for ys in yss] for i in range(len(yss[0]))]

# 3ª solución

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

def agrupa3(xss: list[list[A]]) -> list[list[A]]:

yss = conIgualLongitud(xss)

return list(map(list, zip(*yss)))

# 4ª solución

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

def agrupa4(xss: list[list[A]]) -> list[list[A]]:

yss = conIgualLongitud(xss)

return (transpose(array(yss))).tolist()

# 5ª solución

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

def agrupa5(xss: list[list[A]]) -> list[list[A]]:

yss = conIgualLongitud(xss)

r = []

for i in range(len(yss[0])):

f = []

for xs in xss:

f.append(xs[i])

r.append(f)

return r

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.lists(st.integers()), min_size=1))

def test_agrupa(xss: list[list[int]]) -> None:

r = agrupa1(xss)

assert agrupa2(xss) == r

assert agrupa3(xss) == r

assert agrupa4(xss) == r

assert agrupa5(xss) == r

# La comprobación es

# src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py

# 1 passed in 0.74s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('agrupa1([list(range(10**3)) for _ in range(10**3)])')

# 4.44 segundos

# >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])')

# 0.10 segundos

# >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])')

# 0.10 segundos

# >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])')

# 0.12 segundos

# >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])')

# 0.15 segundos

# >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])')

# 21.25 segundos

# >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])')

# 20.82 segundos

# >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])')

# 13.46 segundos

# >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])')

# 21.70 segundos

# La propiedad es

@given(st.lists(st.lists(st.integers()), min_size=1))

def test_agrupa_length(xss: list[list[int]]) -> None:

n = len(xss)

assert all((len(xs) == n for xs in agrupa2(xss)))

# La comprobación es

# src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py

# 2 passed in 1.25s

Elementos consecutivos relacionados

PorJosé A. Alonso 16-noviembre-202214-diciembre-2022

Definir la función

   relacionados :: (a -> a -> Bool) -> [a] -> Bool

1	relacionados :: (a -> a -> Bool) -> [a] -> Bool

tal que relacionados r xs se verifica si para todo par (x,y) de elementos consecutivos de xs se cumple la relación r. Por ejemplo,

   relacionados (<) [2,3,7,9] == True
   relacionados (<) [2,3,1,9] == False

1 2	relacionados (<) [2,3,7,9] == True relacionados (<) [2,3,1,9] == False

Soluciones

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

Soluciones en Haskell

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

relacionados1 :: (a -> a -> Bool) -> [a] -> Bool
relacionados1 r xs = and [r x y | (x,y) <- zip xs (tail xs)]

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

relacionados2 :: (a -> a -> Bool) -> [a] -> Bool
relacionados2 r (x:y:zs) = r x y && relacionados2 r (y:zs)
relacionados2 _ _        = True

-- 3ª solución
-- ===========

relacionados3 :: (a -> a -> Bool) -> [a] -> Bool
relacionados3 r xs = and (zipWith r xs (tail xs))

-- 4ª solución
-- ===========

relacionados4 :: (a -> a -> Bool) -> [a] -> Bool
relacionados4 r xs = all (uncurry r) (zip xs (tail xs))

-- 1ª solución

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

relacionados1 :: (a -> a -> Bool) -> [a] -> Bool

relacionados1 r xs = and [r x y | (x,y) <- zip xs (tail xs)]

-- 2ª solución

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

relacionados2 :: (a -> a -> Bool) -> [a] -> Bool

relacionados2 r (x:y:zs) = r x y && relacionados2 r (y:zs)

relacionados2 _ _ = True

-- 3ª solución

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

relacionados3 :: (a -> a -> Bool) -> [a] -> Bool

relacionados3 r xs = and (zipWith r xs (tail xs))

-- 4ª solución

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

relacionados4 :: (a -> a -> Bool) -> [a] -> Bool

relacionados4 r xs = all (uncurry r) (zip xs (tail xs))

Soluciones en Python

from typing import Callable, TypeVar

A = TypeVar('A')

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

def relacionados1(r: Callable[[A, A], bool], xs: list[A]) -> bool:
    return all((r(x, y) for (x, y) in zip(xs, xs[1:])))

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

def relacionados2(r: Callable[[A, A], bool], xs: list[A]) -> bool:
    if len(xs) >= 2:
        return r(xs[0], xs[1]) and relacionados1(r, xs[1:])
    return True

from typing import Callable, TypeVar

A = TypeVar('A')

# 1ª solución

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

def relacionados1(r: Callable[[A, A], bool], xs: list[A]) -> bool:

return all((r(x, y) for (x, y) in zip(xs, xs[1:])))

# 2ª solución

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

def relacionados2(r: Callable[[A, A], bool], xs: list[A]) -> bool:

if len(xs) >= 2:

return r(xs[0], xs[1]) and relacionados1(r, xs[1:])

return True

Segmentos cuyos elementos cumplen una propiedad

PorJosé A. Alonso 15-noviembre-202214-diciembre-2022

Definir la función

   segmentos :: (a -> Bool) -> [a] -> [[a]]

1	segmentos :: (a -> Bool) -> [a] -> [[a]]

tal que segmentos p xs es la lista de los segmentos de xs cuyos elementos verifican la propiedad p. Por ejemplo,

   segmentos even [1,2,0,4,9,6,4,5,7,2]  ==  [[2,0,4],[6,4],[2]]
   segmentos odd  [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[9],[5,7]]

1 2	segmentos even [1,2,0,4,9,6,4,5,7,2] == [[2,0,4],[6,4],[2]] segmentos odd [1,2,0,4,9,6,4,5,7,2] == [[1],[9],[5,7]]

Soluciones

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

Soluciones en Haskell

import Data.List.Split (splitWhen)
import Test.QuickCheck.HigherOrder (quickCheck')

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

segmentos1 :: (a -> Bool) -> [a] -> [[a]]
segmentos1 _ [] = []
segmentos1 p (x:xs)
  | p x       = takeWhile p (x:xs) : segmentos1 p (dropWhile p xs)
  | otherwise = segmentos1 p xs

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

segmentos2 :: (a -> Bool) -> [a] -> [[a]]
segmentos2 p xs = filter (not .null) (splitWhen (not . p) xs)

-- 3ª solución
-- ===========

segmentos3 :: (a -> Bool) -> [a] -> [[a]]
segmentos3 = (filter (not . null) .) . splitWhen . (not .)

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

-- La propiedad es
prop_segmentos :: (Int -> Bool) -> [Int] -> Bool
prop_segmentos p xs =
  all (== segmentos1 p xs)
      [segmentos2 p xs,
       segmentos3 p xs]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (segmentos1 even [1..5*10^6])
--    2500000
--    (2.52 secs, 2,080,591,088 bytes)
--    λ> length (segmentos2 even [1..5*10^6])
--    2500000
--    (0.78 secs, 2,860,591,688 bytes)
--    λ> length (segmentos3 even [1..5*10^6])
--    2500000
--    (0.82 secs, 2,860,592,000 bytes)

import Data.List.Split (splitWhen)

import Test.QuickCheck.HigherOrder (quickCheck')

-- 1ª solución

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

segmentos1 :: (a -> Bool) -> [a] -> [[a]]

segmentos1 _ [] = []

segmentos1 p (x:xs)

| p x = takeWhile p (x:xs) : segmentos1 p (dropWhile p xs)

| otherwise = segmentos1 p xs

-- 2ª solución

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

segmentos2 :: (a -> Bool) -> [a] -> [[a]]

segmentos2 p xs = filter (not .null) (splitWhen (not . p) xs)

-- 3ª solución

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

segmentos3 :: (a -> Bool) -> [a] -> [[a]]

segmentos3 = (filter (not . null) .) . splitWhen . (not .)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_segmentos :: (Int -> Bool) -> [Int] -> Bool

prop_segmentos p xs =

all (== segmentos1 p xs)

[segmentos2 p xs,

segmentos3 p xs]

-- La comprobación es

-- λ> quickCheck' prop_segmentos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (segmentos1 even [1..5*10^6])

-- 2500000

-- (2.52 secs, 2,080,591,088 bytes)

-- λ> length (segmentos2 even [1..5*10^6])

-- 2500000

-- (0.78 secs, 2,860,591,688 bytes)

-- λ> length (segmentos3 even [1..5*10^6])

-- 2500000

-- (0.82 secs, 2,860,592,000 bytes)

Soluciones en Python

from itertools import dropwhile, takewhile
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Callable, TypeVar

from more_itertools import split_at

setrecursionlimit(10**6)

A = TypeVar('A')

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

def segmentos1(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:
    if not xs:
        return []
    if p(xs[0]):
        return [list(takewhile(p, xs))] + \
            segmentos1(p, list(dropwhile(p, xs[1:])))
    return segmentos1(p, xs[1:])

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

def segmentos2(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:
    return list(filter((lambda x: x), split_at(xs, lambda x: not p(x))))

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('segmentos1(lambda x: x % 2 == 0, range(10**4))')
#    0.55 segundos
#    >>> tiempo('segmentos2(lambda x: x % 2 == 0, range(10**4))')
#    0.00 segundos

from itertools import dropwhile, takewhile

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Callable, TypeVar

from more_itertools import split_at

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

def segmentos1(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:

if not xs:

return []

if p(xs[0]):

return [list(takewhile(p, xs))] + \

segmentos1(p, list(dropwhile(p, xs[1:])))

return segmentos1(p, xs[1:])

# 2ª solución

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

def segmentos2(p: Callable[[A], bool], xs: list[A]) -> list[list[A]]:

return list(filter((lambda x: x), split_at(xs, lambda x: not p(x))))

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('segmentos1(lambda x: x % 2 == 0, range(10**4))')

# 0.55 segundos

# >>> tiempo('segmentos2(lambda x: x % 2 == 0, range(10**4))')

# 0.00 segundos

Reconocimiento de subcadenas

PorJosé A. Alonso 14-noviembre-202214-diciembre-2022

Definir, por recursión, la función

   esSubcadena :: String -> String -> Bool

1	esSubcadena :: String -> String -> Bool

tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo,

   esSubcadena "casa" "escasamente"   ==  True
   esSubcadena "cante" "escasamente"  ==  False
   esSubcadena "" ""                  ==  True

esSubcadena "casa" "escasamente" == True

esSubcadena "cante" "escasamente" == False

esSubcadena "" "" == True

Soluciones

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

Soluciones en Haskell

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

esSubcadena1 :: String -> String -> Bool
esSubcadena1 [] _      = True
esSubcadena1  _ []     = False
esSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys

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

esSubcadena2 :: String -> String -> Bool
esSubcadena2 xs ys =
  or [xs `isPrefixOf` zs | zs <- sufijos ys]

-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,
--    sufijos "abc"  ==  ["abc","bc","c",""]
sufijos :: String -> [String]
sufijos xs = [drop i xs | i <- [0..length xs]]

-- 3ª solución
-- ===========

esSubcadena3 :: String -> String -> Bool
esSubcadena3 xs ys =
  or [xs `isPrefixOf` zs | zs <- tails ys]

-- 4ª solución
-- ===========

esSubcadena4 :: String -> String -> Bool
esSubcadena4 xs ys =
  any (xs `isPrefixOf`) (tails ys)

-- 5ª solución
-- ===========

esSubcadena5 :: String -> String -> Bool
esSubcadena5 = (. tails) . any . isPrefixOf

-- 6ª solución
-- ===========

esSubcadena6 :: String -> String -> Bool
esSubcadena6 = isInfixOf

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

-- La propiedad es
prop_esSubcadena :: String -> String -> Bool
prop_esSubcadena xs ys =
  all (== esSubcadena1 xs ys)
      [esSubcadena2 xs ys,
       esSubcadena3 xs ys,
       esSubcadena4 xs ys,
       esSubcadena5 xs ys,
       esSubcadena6 xs ys]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> esSubcadena1 "abc" (replicate (5*10^4) 'd' ++ "abc")
--    True
--    (0.03 secs, 17,789,392 bytes)
--    λ> esSubcadena2 "abc" (replicate (5*10^4) 'd' ++ "abc")
--    True
--    (6.32 secs, 24,989,912 bytes)
--
--    λ> esSubcadena1 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (3.24 secs, 1,720,589,432 bytes)
--    λ> esSubcadena3 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (1.81 secs, 1,720,589,656 bytes)
--    λ> esSubcadena4 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.71 secs, 1,120,589,480 bytes)
--    λ> esSubcadena5 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.41 secs, 1,120,589,584 bytes)
--    λ> esSubcadena6 "abc" (replicate (5*10^6) 'd' ++ "abc")
--    True
--    (0.11 secs, 560,589,200 bytes)

-- 1ª solución

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

esSubcadena1 :: String -> String -> Bool

esSubcadena1 [] _ = True

esSubcadena1 _ [] = False

esSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys

-- 2ª solución

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

esSubcadena2 :: String -> String -> Bool

esSubcadena2 xs ys =

or [xs `isPrefixOf` zs | zs <- sufijos ys]

-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,

-- sufijos "abc" == ["abc","bc","c",""]

sufijos :: String -> [String]

sufijos xs = [drop i xs | i <- [0..length xs]]

-- 3ª solución

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

esSubcadena3 :: String -> String -> Bool

esSubcadena3 xs ys =

or [xs `isPrefixOf` zs | zs <- tails ys]

-- 4ª solución

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

esSubcadena4 :: String -> String -> Bool

esSubcadena4 xs ys =

any (xs `isPrefixOf`) (tails ys)

-- 5ª solución

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

esSubcadena5 :: String -> String -> Bool

esSubcadena5 = (. tails) . any . isPrefixOf

-- 6ª solución

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

esSubcadena6 :: String -> String -> Bool

esSubcadena6 = isInfixOf

-- Comprobación de equivalencia

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

-- La propiedad es

prop_esSubcadena :: String -> String -> Bool

prop_esSubcadena xs ys =

all (== esSubcadena1 xs ys)

[esSubcadena2 xs ys,

esSubcadena3 xs ys,

esSubcadena4 xs ys,

esSubcadena5 xs ys,

esSubcadena6 xs ys]

-- La comprobación es

-- λ> quickCheck prop_esSubcadena

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esSubcadena1 "abc" (replicate (5*10^4) 'd' ++ "abc")

-- True

-- (0.03 secs, 17,789,392 bytes)

-- λ> esSubcadena2 "abc" (replicate (5*10^4) 'd' ++ "abc")

-- True

-- (6.32 secs, 24,989,912 bytes)

-- λ> esSubcadena1 "abc" (replicate (5*10^6) 'd' ++ "abc")

-- True

-- (3.24 secs, 1,720,589,432 bytes)

-- λ> esSubcadena3 "abc" (replicate (5*10^6) 'd' ++ "abc")

-- True

-- (1.81 secs, 1,720,589,656 bytes)

-- λ> esSubcadena4 "abc" (replicate (5*10^6) 'd' ++ "abc")

-- True

-- (0.71 secs, 1,120,589,480 bytes)

-- λ> esSubcadena5 "abc" (replicate (5*10^6) 'd' ++ "abc")

-- True

-- (0.41 secs, 1,120,589,584 bytes)

-- λ> esSubcadena6 "abc" (replicate (5*10^6) 'd' ++ "abc")

-- True

-- (0.11 secs, 560,589,200 bytes)

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

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

def esSubcadena1(xs: str, ys: str) -> bool:
    if not xs:
        return True
    if not ys:
        return False
    return ys.startswith(xs) or esSubcadena1(xs, ys[1:])

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

# sufijos(xs) es la lista de sufijos de xs. Por ejemplo,
#    sufijos("abc")  ==  ['abc', 'bc', 'c', '']
def sufijos(xs: str) -> list[str]:
    return [xs[i:] for i in range(len(xs) + 1)]

def esSubcadena2(xs: str, ys: str) -> bool:
    return any(zs.startswith(xs) for zs in sufijos(ys))

# 3ª solución
# ===========

def esSubcadena3(xs: str, ys: str) -> bool:
    return xs in ys

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

# La propiedad es
@given(st.text(), st.text())
def test_esSubcadena(xs: str, ys: str) -> None:
    r = esSubcadena1(xs, ys)
    assert esSubcadena2(xs, ys) == r
    assert esSubcadena3(xs, ys) == r

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

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('esSubcadena1("abc", "d"*(10**4) + "abc")')
#    0.02 segundos
#    >>> tiempo('esSubcadena2("abc", "d"*(10**4) + "abc")')
#    0.01 segundos
#    >>> tiempo('esSubcadena3("abc", "d"*(10**4) + "abc")')
#    0.00 segundos
#
#    >>> tiempo('esSubcadena2("abc", "d"*(10**5) + "abc")')
#    1.74 segundos
#    >>> tiempo('esSubcadena3("abc", "d"*(10**5) + "abc")')
#    0.00 segundos

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def esSubcadena1(xs: str, ys: str) -> bool:

if not xs:

return True

if not ys:

return False

return ys.startswith(xs) or esSubcadena1(xs, ys[1:])

# 2ª solución

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

# sufijos(xs) es la lista de sufijos de xs. Por ejemplo,

# sufijos("abc") == ['abc', 'bc', 'c', '']

def sufijos(xs: str) -> list[str]:

return [xs[i:] for i in range(len(xs) + 1)]

def esSubcadena2(xs: str, ys: str) -> bool:

return any(zs.startswith(xs) for zs in sufijos(ys))

# 3ª solución

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

def esSubcadena3(xs: str, ys: str) -> bool:

return xs in ys

# Comprobación de equivalencia

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

# La propiedad es

@given(st.text(), st.text())

def test_esSubcadena(xs: str, ys: str) -> None:

r = esSubcadena1(xs, ys)

assert esSubcadena2(xs, ys) == r

assert esSubcadena3(xs, ys) == r

# La comprobación es

# src> poetry run pytest -q reconocimiento_de_subcadenas.py

# 1 passed in 0.35s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('esSubcadena1("abc", "d"*(10**4) + "abc")')

# 0.02 segundos

# >>> tiempo('esSubcadena2("abc", "d"*(10**4) + "abc")')

# 0.01 segundos

# >>> tiempo('esSubcadena3("abc", "d"*(10**4) + "abc")')

# 0.00 segundos

# >>> tiempo('esSubcadena2("abc", "d"*(10**5) + "abc")')

# 1.74 segundos

# >>> tiempo('esSubcadena3("abc", "d"*(10**5) + "abc")')

# 0.00 segundos

1. El tipo de los árboles binarios en Haskell

2. El tipo de los árboles binarios en Python

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

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

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

1. El tipo de las fórmulas proposicionales en Haskell

1. El tipo de las fórmulas proposicionales en Haskell

Entradas recientes

Buscar

Correo electrónico