noviembre 2022 – Exercitium

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

Posiciones de un carácter en una cadena

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

Definir la función

   posiciones :: Char -> String -> [Int]

1	posiciones :: Char -> String -> [Int]

tal que posiciones x ys es la lista de la posiciones del carácter x en la cadena ys. Por ejemplo,

   posiciones 'a' "Salamamca"   ==  [1,3,5,8]

1	posiciones 'a' "Salamamca" == [1,3,5,8]

Soluciones

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

Soluciones en Haskell

import Data.List (elemIndices)
import Test.QuickCheck

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

posiciones1 :: Char -> String -> [Int]
posiciones1 x ys = [n | (y,n) <- zip ys [0..], y == x]

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

posiciones2 :: Char -> String -> [Int]
posiciones2 x ys = aux x ys 0
  where
    aux _ [] _ = []
    aux b (a:as) n | a == b    = n : aux b as (n+1)
                   | otherwise = aux b as (n+1)

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

posiciones3 :: Char -> String -> [Int]
posiciones3 = elemIndices

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

-- La propiedad es
prop_posiciones :: Char -> String -> Bool
prop_posiciones x ys =
  all (== posiciones1 x ys)
      [posiciones2 x ys,
       posiciones3 x ys]

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

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

-- La comparación es
--    λ> length (posiciones1 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (2.48 secs, 1,680,591,672 bytes)
--    λ> length (posiciones2 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (2.98 secs, 1,584,591,720 bytes)
--    λ> length (posiciones3 'a' (take (6*10^6) (cycle "abc")))
--    2000000
--    (0.11 secs, 496,591,600 bytes)

import Data.List (elemIndices)

import Test.QuickCheck

-- 1ª solución

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

posiciones1 :: Char -> String -> [Int]

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

-- 2ª solución

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

posiciones2 :: Char -> String -> [Int]

posiciones2 x ys = aux x ys 0

where

aux _ [] _ = []

aux b (a:as) n | a == b = n : aux b as (n+1)

| otherwise = aux b as (n+1)

-- 3ª solución

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

posiciones3 :: Char -> String -> [Int]

posiciones3 = elemIndices

-- Comprobación de equivalencia

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

-- La propiedad es

prop_posiciones :: Char -> String -> Bool

prop_posiciones x ys =

all (== posiciones1 x ys)

[posiciones2 x ys,

posiciones3 x ys]

-- La comprobación es

-- λ> quickCheck prop_posiciones

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (posiciones1 'a' (take (6*10^6) (cycle "abc")))

-- 2000000

-- (2.48 secs, 1,680,591,672 bytes)

-- λ> length (posiciones2 'a' (take (6*10^6) (cycle "abc")))

-- 2000000

-- (2.98 secs, 1,584,591,720 bytes)

-- λ> length (posiciones3 'a' (take (6*10^6) (cycle "abc")))

-- 2000000

-- (0.11 secs, 496,591,600 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 posiciones1(x: str, ys: str) -> list[int]:
    return [n for (n, y) in enumerate(ys) if y == x]

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

def posiciones2(x: str, ys: str) -> list[int]:
    def aux(a: str, bs: str, n: int) -> list[int]:
        if bs:
            if a == bs[0]:
                return [n] + aux(a, bs[1:], n + 1)
            return aux(a, bs[1:], n + 1)
        return []
    return aux(x, ys, 0)

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

def posiciones3(x: str, ys: str) -> list[int]:
    r = []
    for n, y in enumerate(ys):
        if x == y:
            r.append(n)
    return r

# La propiedad es
@given(st.text(), st.text())
def test_posiciones(x: str, ys: str) -> None:
    r = posiciones1(x, ys)
    assert posiciones2(x, ys) == r
    assert posiciones3(x, ys) == r

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

# 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('posiciones1("a", "abc"*6000)')
#    0.00 segundos
#    >>> tiempo('posiciones2("a", "abc"*6000)')
#    0.06 segundos
#    >>> tiempo('posiciones3("a", "abc"*6000)')
#    0.00 segundos
#
#    >>> tiempo('posiciones1("a", "abc"*(2*10**7))')
#    3.02 segundos
#    >>> tiempo('posiciones3("a", "abc"*(2*10**7))')
#    3.47 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 posiciones1(x: str, ys: str) -> list[int]:

return [n for (n, y) in enumerate(ys) if y == x]

# -- 2ª solución

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

def posiciones2(x: str, ys: str) -> list[int]:

def aux(a: str, bs: str, n: int) -> list[int]:

if bs:

if a == bs[0]:

return [n] + aux(a, bs[1:], n + 1)

return aux(a, bs[1:], n + 1)

return []

return aux(x, ys, 0)

# -- 3ª solución

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

def posiciones3(x: str, ys: str) -> list[int]:

r = []

for n, y in enumerate(ys):

if x == y:

r.append(n)

return r

# La propiedad es

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

def test_posiciones(x: str, ys: str) -> None:

r = posiciones1(x, ys)

assert posiciones2(x, ys) == r

assert posiciones3(x, ys) == r

# La comprobación es

# src> poetry run pytest -q posiciones_de_un_caracter_en_una_cadena.py

# 1 passed in 0.29s

# 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('posiciones1("a", "abc"*6000)')

# 0.00 segundos

# >>> tiempo('posiciones2("a", "abc"*6000)')

# 0.06 segundos

# >>> tiempo('posiciones3("a", "abc"*6000)')

# 0.00 segundos

# >>> tiempo('posiciones1("a", "abc"*(2*10**7))')

# 3.02 segundos

# >>> tiempo('posiciones3("a", "abc"*(2*10**7))')

# 3.47 segundos

Mayúsculas iniciales

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

Se consideran las siguientes reglas de mayúsculas iniciales para los títulos:

la primera palabra comienza en mayúscula y
todas las palabras que tienen 4 letras como mínimo empiezan con mayúsculas

Definir la función

   titulo :: [String] -> [String]

1	titulo :: [String] -> [String]

tal que titulo ps es la lista de las palabras de ps con las reglas de mayúsculas iniciales de los títulos. Por ejemplo,

   λ> titulo ["eL","arTE","DE","La","proGraMacion"]
   ["El","Arte","de","la","Programacion"]

1 2	λ> titulo ["eL","arTE","DE","La","proGraMacion"] ["El","Arte","de","la","Programacion"]

Soluciones

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

Soluciones en Haskell

import Data.Char (toUpper, toLower)
import Test.QuickCheck

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

titulo1 :: [String] -> [String]
titulo1 []     = []
titulo1 (p:ps) = mayusculaInicial p : [transforma q | q <- ps]

-- (mayusculaInicial xs) es la palabra xs con la letra inicial
-- en mayúscula y las restantes en minúsculas. Por ejemplo,
--    mayusculaInicial "sEviLLa"  ==  "Sevilla"
mayusculaInicial :: String -> String
mayusculaInicial []     = []
mayusculaInicial (x:xs) = toUpper x : [toLower y | y <- xs]

-- (transforma p) es la palabra p con mayúscula inicial si su longitud
-- es mayor o igual que 4 y es p en minúscula en caso contrario
transforma :: String -> String
transforma p | length p >= 4 = mayusculaInicial p
             | otherwise     = minuscula p

-- (minuscula xs) es la palabra xs en minúscula.
minuscula :: String -> String
minuscula xs = [toLower x | x <- xs]

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

titulo2 :: [String] -> [String]
titulo2 []     = []
titulo2 (p:ps) = mayusculaInicial p : aux ps
  where aux []     = []
        aux (q:qs) = transforma q : aux qs

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

titulo3 :: [String] -> [String]
titulo3 []     = []
titulo3 (p:ps) = mayusculaInicial p : map transforma ps

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

-- La propiedad es
prop_titulo :: [String] -> Bool
prop_titulo xs =
  all (== titulo1 xs)
      [titulo2 xs,
       titulo3 xs]

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

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

-- La comparación es
--    λ> length (titulo1 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (2.17 secs, 1,680,592,512 bytes)
--    λ> length (titulo2 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (2.45 secs, 2,240,592,464 bytes)
--    λ> length (titulo3 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))
--    10000000
--    (0.16 secs, 1,440,592,464 bytes)

import Data.Char (toUpper, toLower)

import Test.QuickCheck

-- 1ª solución

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

titulo1 :: [String] -> [String]

titulo1 [] = []

titulo1 (p:ps) = mayusculaInicial p : [transforma q | q <- ps]

-- (mayusculaInicial xs) es la palabra xs con la letra inicial

-- en mayúscula y las restantes en minúsculas. Por ejemplo,

-- mayusculaInicial "sEviLLa" == "Sevilla"

mayusculaInicial :: String -> String

mayusculaInicial [] = []

mayusculaInicial (x:xs) = toUpper x : [toLower y | y <- xs]

-- (transforma p) es la palabra p con mayúscula inicial si su longitud

-- es mayor o igual que 4 y es p en minúscula en caso contrario

transforma :: String -> String

transforma p | length p >= 4 = mayusculaInicial p

| otherwise = minuscula p

-- (minuscula xs) es la palabra xs en minúscula.

minuscula :: String -> String

minuscula xs = [toLower x | x <- xs]

-- 2ª solución

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

titulo2 :: [String] -> [String]

titulo2 [] = []

titulo2 (p:ps) = mayusculaInicial p : aux ps

where aux [] = []

aux (q:qs) = transforma q : aux qs

-- 3ª solución

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

titulo3 :: [String] -> [String]

titulo3 [] = []

titulo3 (p:ps) = mayusculaInicial p : map transforma ps

-- Comprobación de equivalencia

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

-- La propiedad es

prop_titulo :: [String] -> Bool

prop_titulo xs =

all (== titulo1 xs)

[titulo2 xs,

titulo3 xs]

-- La comprobación es

-- λ> quickCheck prop_titulo

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (titulo1 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))

-- 10000000

-- (2.17 secs, 1,680,592,512 bytes)

-- λ> length (titulo2 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))

-- 10000000

-- (2.45 secs, 2,240,592,464 bytes)

-- λ> length (titulo3 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre"])))

-- 10000000

-- (0.16 secs, 1,440,592,464 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
# ===========

# (mayusculaInicial xs) es la palabra xs con la letra inicial
# en mayúscula y las restantes en minúsculas. Por ejemplo,
#    mayusculaInicial("sEviLLa")  ==  "Sevilla"
def mayusculaInicial(xs: str) -> str:
    return xs.capitalize()

# (minuscula xs) es la palabra xs en minúscula.
def minuscula(xs: str) -> str:
    return xs.lower()

# (transforma p) es la palabra p con mayúscula inicial si su longitud
# es mayor o igual que 4 y es p en minúscula en caso contrario
def transforma(p: str) -> str:
    if len(p) >= 4:
        return mayusculaInicial(p)
    return minuscula(p)

def titulo1(ps: list[str]) -> list[str]:
    if ps:
        return [mayusculaInicial(ps[0])] + [transforma(q) for q in ps[1:]]
    return []

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

def titulo2(ps: list[str]) -> list[str]:
    def aux(qs: list[str]) -> list[str]:
        if qs:
            return [transforma(qs[0])] + aux(qs[1:])
        return []
    if ps:
        return [mayusculaInicial(ps[0])] + aux(ps[1:])
    return []

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

def titulo3(ps: list[str]) -> list[str]:
    if ps:
        return [mayusculaInicial(ps[0])] + list(map(transforma, ps[1:]))
    return []

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

# La propiedad es
@given(st.lists(st.text()))
def test_titulo(ps: list[str]) -> None:
    r = titulo1(ps)
    assert titulo2(ps) == r
    assert titulo3(ps) == r

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

# 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('len(mayusculaInicial1("aB"*(10**7)))')
#    >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.00 segundos
#    >>> tiempo('titulo2(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.30 segundos
#    >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*1900)')
#    0.00 segundos
#
#    >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')
#    2.93 segundos
#    >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')
#    2.35 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

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

# (mayusculaInicial xs) es la palabra xs con la letra inicial

# en mayúscula y las restantes en minúsculas. Por ejemplo,

# mayusculaInicial("sEviLLa") == "Sevilla"

def mayusculaInicial(xs: str) -> str:

return xs.capitalize()

# (minuscula xs) es la palabra xs en minúscula.

def minuscula(xs: str) -> str:

return xs.lower()

# (transforma p) es la palabra p con mayúscula inicial si su longitud

# es mayor o igual que 4 y es p en minúscula en caso contrario

def transforma(p: str) -> str:

if len(p) >= 4:

return mayusculaInicial(p)

return minuscula(p)

def titulo1(ps: list[str]) -> list[str]:

if ps:

return [mayusculaInicial(ps[0])] + [transforma(q) for q in ps[1:]]

return []

# 2ª solución

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

def titulo2(ps: list[str]) -> list[str]:

def aux(qs: list[str]) -> list[str]:

if qs:

return [transforma(qs[0])] + aux(qs[1:])

return []

if ps:

return [mayusculaInicial(ps[0])] + aux(ps[1:])

return []

# 3ª solución

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

def titulo3(ps: list[str]) -> list[str]:

if ps:

return [mayusculaInicial(ps[0])] + list(map(transforma, ps[1:]))

return []

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.text()))

def test_titulo(ps: list[str]) -> None:

r = titulo1(ps)

assert titulo2(ps) == r

assert titulo3(ps) == r

# La comprobación es

# src> poetry run pytest -q mayusculas_iniciales.py

# 1 passed in 0.55s

# 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('len(mayusculaInicial1("aB"*(10**7)))')

# >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*1900)')

# 0.00 segundos

# >>> tiempo('titulo2(["eL","arTE","DE","La","proGraMacion "]*1900)')

# 0.30 segundos

# >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*1900)')

# 0.00 segundos

# >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')

# 2.93 segundos

# >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion "]*(2*10**6))')

# 2.35 segundos

Poner en mayúscula la primera letra y las restantes en minúsculas

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

Definir la función

   mayusculaInicial :: String -> String

1	mayusculaInicial :: String -> String

tal que mayusculaInicial xs es la palabra xs con la letra inicial en mayúscula y las restantes en minúsculas. Por ejemplo,

   mayusculaInicial "sEviLLa"  ==  "Sevilla"
   mayusculaInicial ""         ==  ""

1 2	mayusculaInicial "sEviLLa" == "Sevilla" mayusculaInicial "" == ""

Soluciones

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

Soluciones en Haskell

import Data.Char (toUpper, toLower)
import Test.QuickCheck

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

mayusculaInicial1 :: String -> String
mayusculaInicial1 []     = []
mayusculaInicial1 (x:xs) = toUpper x : [toLower y | y <- xs]

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

mayusculaInicial2 :: String -> String
mayusculaInicial2 [] = []
mayusculaInicial2 (x:xs) = toUpper x : aux xs
  where aux (y:ys) = toLower y : aux ys
        aux []     = []

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

mayusculaInicial3 :: String -> String
mayusculaInicial3 [] = []
mayusculaInicial3 (x:xs) = toUpper x : map toLower xs

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

-- La propiedad es
prop_mayusculaInicial :: String -> Bool
prop_mayusculaInicial xs =
  all (== mayusculaInicial1 xs)
      [mayusculaInicial2 xs,
       mayusculaInicial3 xs]

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

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

-- La comparación es
--    λ> length (mayusculaInicial1 (take (10^7) (cycle "aA")))
--    10000000
--    (2.22 secs, 1,680,592,240 bytes)
--    λ> length (mayusculaInicial2 (take (10^7) (cycle "aA")))
--    10000000
--    (2.57 secs, 2,240,592,192 bytes)
--    λ> length (mayusculaInicial3 (take (10^7) (cycle "aA")))
--    10000000
--    (0.16 secs, 1,440,592,192 bytes)

import Data.Char (toUpper, toLower)

import Test.QuickCheck

-- 1ª solución

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

mayusculaInicial1 :: String -> String

mayusculaInicial1 [] = []

mayusculaInicial1 (x:xs) = toUpper x : [toLower y | y <- xs]

-- 2ª solución

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

mayusculaInicial2 :: String -> String

mayusculaInicial2 [] = []

mayusculaInicial2 (x:xs) = toUpper x : aux xs

where aux (y:ys) = toLower y : aux ys

aux [] = []

-- 3ª solución

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

mayusculaInicial3 :: String -> String

mayusculaInicial3 [] = []

mayusculaInicial3 (x:xs) = toUpper x : map toLower xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_mayusculaInicial :: String -> Bool

prop_mayusculaInicial xs =

all (== mayusculaInicial1 xs)

[mayusculaInicial2 xs,

mayusculaInicial3 xs]

-- La comprobación es

-- λ> quickCheck prop_mayusculaInicial

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (mayusculaInicial1 (take (10^7) (cycle "aA")))

-- 10000000

-- (2.22 secs, 1,680,592,240 bytes)

-- λ> length (mayusculaInicial2 (take (10^7) (cycle "aA")))

-- 10000000

-- (2.57 secs, 2,240,592,192 bytes)

-- λ> length (mayusculaInicial3 (take (10^7) (cycle "aA")))

-- 10000000

-- (0.16 secs, 1,440,592,192 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 mayusculaInicial1(xs: str) -> str:
    if xs:
        return "".join([xs[0].upper()] + [y.lower() for y in xs[1:]])
    return ""

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

def mayusculaInicial2(xs: str) -> str:
    def aux(ys: str) -> str:
        if ys:
            return ys[0].lower() + aux(ys[1:])
        return ""
    if xs:
        return "".join(xs[0].upper() + aux(xs[1:]))
    return ""

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

def mayusculaInicial3(xs: str) -> str:
    if xs:
        return "".join([xs[0].upper()] + list(map(str.lower, xs[1:])))
    return ""

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

def mayusculaInicial4(xs: str) -> str:
    return xs.capitalize()

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

# La propiedad es
@given(st.text())
def test_mayusculaInicial(xs: str) -> None:
    r = mayusculaInicial1(xs)
    assert mayusculaInicial2(xs) == r
    assert mayusculaInicial3(xs) == r

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

# 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('len(mayusculaInicial1("aB"*(10**7)))')
#    1.92 segundos
#    >>> tiempo('len(mayusculaInicial2("aB"*(10**7)))')
#    Process Python terminado (killed)
#    >>> tiempo('len(mayusculaInicial3("aB"*(10**7)))')
#    1.59 segundos
#    >>> tiempo('len(mayusculaInicial4("aB"*(10**7)))')
#    0.13 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 mayusculaInicial1(xs: str) -> str:

if xs:

return "".join([xs[0].upper()] + [y.lower() for y in xs[1:]])

return ""

# 2ª solución

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

def mayusculaInicial2(xs: str) -> str:

def aux(ys: str) -> str:

if ys:

return ys[0].lower() + aux(ys[1:])

return ""

if xs:

return "".join(xs[0].upper() + aux(xs[1:]))

return ""

# 3ª solución

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

def mayusculaInicial3(xs: str) -> str:

if xs:

return "".join([xs[0].upper()] + list(map(str.lower, xs[1:])))

return ""

# 4ª solución

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

def mayusculaInicial4(xs: str) -> str:

return xs.capitalize()

# Comprobación de equivalencia

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

# La propiedad es

@given(st.text())

def test_mayusculaInicial(xs: str) -> None:

r = mayusculaInicial1(xs)

assert mayusculaInicial2(xs) == r

assert mayusculaInicial3(xs) == r

# La comprobación es

# src> poetry run pytest -q mayuscula_inicial.py

# 1 passed in 0.26s

# 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('len(mayusculaInicial1("aB"*(10**7)))')

# 1.92 segundos

# >>> tiempo('len(mayusculaInicial2("aB"*(10**7)))')

# Process Python terminado (killed)

# >>> tiempo('len(mayusculaInicial3("aB"*(10**7)))')

# 1.59 segundos

# >>> tiempo('len(mayusculaInicial4("aB"*(10**7)))')

# 0.13 segundos

Suma de los dígitos de una cadena

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

Definir la función

   sumaDigitos :: String -> Int

1	sumaDigitos :: String -> Int

tal que sumaDigitos xs' es la suma de los dígitos de la cadenaxs`. Por ejemplo,

   sumaDigitos "SE 2431 X"  ==  10

1	sumaDigitos "SE 2431 X" == 10

Soluciones

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

Soluciones en Haskell

import Data.Char (digitToInt, isDigit)
import Test.QuickCheck

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

sumaDigitos1 :: String -> Int
sumaDigitos1 xs = sum [digitToInt x | x <- xs, isDigit x]

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

sumaDigitos2 :: String -> Int
sumaDigitos2 [] = 0
sumaDigitos2 (x:xs)
  | isDigit x  = digitToInt x + sumaDigitos2 xs
  | otherwise  = sumaDigitos2 xs

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

sumaDigitos3 :: String -> Int
sumaDigitos3 xs = sum (map digitToInt (filter isDigit xs))

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

sumaDigitos4 :: String -> Int
sumaDigitos4 = sum . map digitToInt . filter isDigit

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

-- La propiedad es
prop_sumaDigitos :: String -> Bool
prop_sumaDigitos xs =
  all (== sumaDigitos1 xs)
      [sumaDigitos2 xs,
       sumaDigitos3 xs,
       sumaDigitos4 xs]

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

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

-- La comparación es
--    λ> sumaDigitos1 (take (4*10^6) (cycle "ab12"))
--    3000000
--    (1.92 secs, 819,045,328 bytes)
--    λ> sumaDigitos2 (take (4*10^6) (cycle "ab12"))
--    3000000
--    (1.79 secs, 856,419,112 bytes)
--    λ> sumaDigitos3 (take (4*10^6) (cycle "ab12"))
--    3000000
--    (0.62 secs, 723,045,296 bytes)
--    λ> sumaDigitos4 (take (4*10^6) (cycle "ab12"))
--    3000000
--    (0.63 secs, 723,045,552 bytes)

import Data.Char (digitToInt, isDigit)

import Test.QuickCheck

-- 1ª solución

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

sumaDigitos1 :: String -> Int

sumaDigitos1 xs = sum [digitToInt x | x <- xs, isDigit x]

-- 2ª solución

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

sumaDigitos2 :: String -> Int

sumaDigitos2 [] = 0

sumaDigitos2 (x:xs)

| isDigit x = digitToInt x + sumaDigitos2 xs

| otherwise = sumaDigitos2 xs

-- 3ª solución

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

sumaDigitos3 :: String -> Int

sumaDigitos3 xs = sum (map digitToInt (filter isDigit xs))

-- 4ª solución

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

sumaDigitos4 :: String -> Int

sumaDigitos4 = sum . map digitToInt . filter isDigit

-- Comprobación de equivalencia

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

-- La propiedad es

prop_sumaDigitos :: String -> Bool

prop_sumaDigitos xs =

all (== sumaDigitos1 xs)

[sumaDigitos2 xs,

sumaDigitos3 xs,

sumaDigitos4 xs]

-- La comprobación es

-- λ> quickCheck prop_sumaDigitos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> sumaDigitos1 (take (4*10^6) (cycle "ab12"))

-- 3000000

-- (1.92 secs, 819,045,328 bytes)

-- λ> sumaDigitos2 (take (4*10^6) (cycle "ab12"))

-- 3000000

-- (1.79 secs, 856,419,112 bytes)

-- λ> sumaDigitos3 (take (4*10^6) (cycle "ab12"))

-- 3000000

-- (0.62 secs, 723,045,296 bytes)

-- λ> sumaDigitos4 (take (4*10^6) (cycle "ab12"))

-- 3000000

-- (0.63 secs, 723,045,552 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 sumaDigitos1(xs: str) -> int:
    return sum((int(x) for x in xs if x.isdigit()))

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

def sumaDigitos2(xs: str) -> int:
    if xs:
        if xs[0].isdigit():
            return int(xs[0]) + sumaDigitos2(xs[1:])
        return sumaDigitos2(xs[1:])
    return 0

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

def sumaDigitos3(xs: str) -> int:
    r = 0
    for x in xs:
        if x.isdigit():
            r = r + int(x)
    return r

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

# La propiedad es
@given(st.text())
def test_sumaDigitos(xs: str) -> None:
    r = sumaDigitos1(xs)
    assert sumaDigitos2(xs) == r
    assert sumaDigitos3(xs) == r

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

# 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('mayorExponente1(2, 2**(2*10**4))')


# Comparación de eficiencia
# =========================
#
# La comparación es
#    >>> tiempo('sumaDigitos1("ab12"*5000)')
#    0.00 segundos
#    >>> tiempo('sumaDigitos2("ab12"*5000)')
#    0.02 segundos
#    >>> tiempo('sumaDigitos3("ab12"*5000)')
#    0.00 segundos
#
#    >>> tiempo('sumaDigitos1("ab12"*(5*10**6))')
#    1.60 segundos
#    >>> tiempo('sumaDigitos3("ab12"*(5*10**6))')
#    1.83 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 sumaDigitos1(xs: str) -> int:

return sum((int(x) for x in xs if x.isdigit()))

# 2ª solución

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

def sumaDigitos2(xs: str) -> int:

if xs:

if xs[0].isdigit():

return int(xs[0]) + sumaDigitos2(xs[1:])

return sumaDigitos2(xs[1:])

return 0

# 3ª solución

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

def sumaDigitos3(xs: str) -> int:

r = 0

for x in xs:

if x.isdigit():

r = r + int(x)

return r

# Comprobación de equivalencia

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

# La propiedad es

@given(st.text())

def test_sumaDigitos(xs: str) -> None:

r = sumaDigitos1(xs)

assert sumaDigitos2(xs) == r

assert sumaDigitos3(xs) == r

# La comprobación es

# src> poetry run pytest -q suma_de_digitos_de_cadena.py

# 1 passed in 0.41s

# 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('mayorExponente1(2, 2**(2*10**4))')

# Comparación de eficiencia

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

# La comparación es

# >>> tiempo('sumaDigitos1("ab12"*5000)')

# 0.00 segundos

# >>> tiempo('sumaDigitos2("ab12"*5000)')

# 0.02 segundos

# >>> tiempo('sumaDigitos3("ab12"*5000)')

# 0.00 segundos

# >>> tiempo('sumaDigitos1("ab12"*(5*10**6))')

# 1.60 segundos

# >>> tiempo('sumaDigitos3("ab12"*(5*10**6))')

# 1.83 segundos

Números de Lychrel

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

Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel:
+ 56, ya que en un paso se obtiene un capicúa: 56+65=121.
+ 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363
+ 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111
+ 89, ya que en 24 pasos se obtiene un capicúa.
En esta serie de ejercicios vamos a buscar el primer número de Lychrel.

Ejercicio 1. Definir la función

   esCapicua :: Integer -> Bool

1	esCapicua :: Integer -> Bool

tal que esCapicua x se verifica si x es capicúa. Por ejemplo,

   esCapicua 252  ==  True
   esCapicua 253  ==  False

1 2	esCapicua 252 == True esCapicua 253 == False

Ejercicio 2. Definir la función

   inverso :: Integer -> Integer

1	inverso :: Integer -> Integer

tal que inverso x es el número obtenido escribiendo las cifras de x en orden inverso. Por ejemplo,

   inverso 253  ==  352

1	inverso 253 == 352

Ejercicio 3. Definir la función

   siguiente :: Integer -> Integer

1	siguiente :: Integer -> Integer

tal que siguiente x es el número obtenido sumándole a x su inverso. Por ejemplo,

   siguiente 253  ==  605

1	siguiente 253 == 605

Ejercicio 4. Definir la función

   busquedaDeCapicua :: Integer -> [Integer]

1	busquedaDeCapicua :: Integer -> [Integer]

tal que busquedaDeCapicua x es la lista de los números tal que el primero es x, el segundo es el siguiente de x y así sucesivamente hasta que se alcanza un capicúa. Por ejemplo,

   busquedaDeCapicua 253  ==  [253,605,1111]

1	busquedaDeCapicua 253 == [253,605,1111]

Ejercicio 5. Definir la función

   capicuaFinal :: Integer -> Integer

1	capicuaFinal :: Integer -> Integer

tal que capicuaFinal x es la capicúa con la que termina la búsqueda de capicúa a partir de x. Por ejemplo,

   capicuaFinal 253  ==  1111

1	capicuaFinal 253 == 1111

Ejercicio 6. Definir la función

   orden :: Integer -> Integer

1	orden :: Integer -> Integer

tal que orden x es el número de veces que se repite el proceso de calcular el inverso a partir de x hasta alcanzar un número capicúa. Por ejemplo,

   orden 253  ==  2

1	orden 253 == 2

Ejercicio 7. Definir la función

   ordenMayor :: Integer -> Integer -> Bool

1	ordenMayor :: Integer -> Integer -> Bool

tal que ordenMayor x n se verifica si el orden de x es mayor o igual que n. Dar la definición sin necesidad de evaluar el orden de x. Por ejemplo,

   λ> ordenMayor 1186060307891929990 2
   True
   λ> orden 1186060307891929990
   261

λ> ordenMayor 1186060307891929990 2

True

λ> orden 1186060307891929990

261

Ejercicio 8. Definir la función

   ordenEntre :: Integer -> Integer -> [Integer]

1	ordenEntre :: Integer -> Integer -> [Integer]

tal que ordenEntre m n es la lista de los elementos cuyo orden esmayor o igual que m y menor que n. Por ejemplo,

   take 5 (ordenEntre 10 11)  ==  [829,928,9059,9149,9239]

1	take 5 (ordenEntre 10 11) == [829,928,9059,9149,9239]

Ejercicio 9. Definir la función

   menorDeOrdenMayor :: Integer -> Integer

1	menorDeOrdenMayor :: Integer -> Integer

tal que menorDeOrdenMayor n es el menor elemento cuyo orden es mayor que n. Por ejemplo,

   menorDeOrdenMayor 2   ==  19
   menorDeOrdenMayor 20  ==  89

1 2	menorDeOrdenMayor 2 == 19 menorDeOrdenMayor 20 == 89

Ejercicio 10. Definir la función

   menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]

1	menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]

tal que menoresdDeOrdenMayor m es la lista de los pares (n,x) tales que n es un número entre 1 y m y x es el menor elemento de orden mayor que n. Por ejemplo,

   menoresdDeOrdenMayor 5  ==  [(1,10),(2,19),(3,59),(4,69),(5,79)]

1	menoresdDeOrdenMayor 5 == [(1,10),(2,19),(3,59),(4,69),(5,79)]

Ejercicio 11. A la vista de los resultados de menoresdDeOrdenMayor 5 conjeturar sobre la última cifra de menorDeOrdenMayor.

Ejercicio 12. Decidir con QuickCheck la conjetura.

Ejercicio 13. Calcular menoresdDeOrdenMayor 50

Ejercicio 14. A la vista de menoresdDeOrdenMayor 50, conjeturar el orden de 196.

Ejercicio 15. Comprobar con QuickCheck la conjetura sobre el orden de 196.

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

-- Solución de ejercicio 1
esCapicua :: Integer -> Bool
esCapicua x = x' == reverse x'
  where x' = show x

-- Solución de ejercicio 2
inverso :: Integer -> Integer
inverso = read . reverse . show

-- Solución de ejercicio 3
siguiente :: Integer -> Integer
siguiente x = x + inverso x

-- Solución de ejercicio 4
busquedaDeCapicua :: Integer -> [Integer]
busquedaDeCapicua x | esCapicua x = [x]
                    | otherwise   = x : busquedaDeCapicua (siguiente x)

-- Solución de ejercicio 5
capicuaFinal :: Integer -> Integer
capicuaFinal x = last (busquedaDeCapicua x)

-- Solución de ejercicio 6
orden :: Integer -> Integer
orden x | esCapicua x = 0
        | otherwise   = 1 + orden (siguiente x)

-- Solución de ejercicio 7
ordenMayor :: Integer -> Integer -> Bool
ordenMayor x n | esCapicua x = n == 0
               | n <= 0      = True
               | otherwise   = ordenMayor (siguiente x) (n-1)

-- Solución de ejercicio 8
ordenEntre :: Integer -> Integer -> [Integer]
ordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]

-- Solución de ejercicio 9
menorDeOrdenMayor :: Integer -> Integer
menorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]

-- Solución de ejercicio 10
menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]
menoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]

-- Solución de ejercicio 11
-- La conjetura es que para n mayor que 1, la última cifra de
-- (menorDeOrdenMayor n) es 9.

-- Solución de ejercicio 12
-- ========================

-- La conjetura es
prop_menorDeOrdenMayor :: Integer -> Property
prop_menorDeOrdenMayor n =
  n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9

-- La comprobación es
--    λ> quickCheck prop_menorDeOrdenMayor
--    *** Failed! Falsifiable (after 22 tests and 2 shrinks):
--    25

-- Se puede comprobar que 25 es un contraejemplo,
--    λ> menorDeOrdenMayor 25
--    196

-- Solución de ejercicio 13
-- El cálculo es
--    λ> menoresdDeOrdenMayor 50
--    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
--     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
--     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
--     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
--     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
--     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
--     (47,196),(48,196),(49,196),(50,196)]

-- Solución de ejercicio 14
-- La conjetura es que el orden de 196 es infinito y, por tanto,
-- 196 es un número del Lychrel.

-- Solución de ejercicio 15
-- ========================

-- La propiedad es
prop_ordenDe196 :: Integer -> Bool
prop_ordenDe196 n =
  ordenMayor 196 n

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

import Test.QuickCheck

-- Solución de ejercicio 1

esCapicua :: Integer -> Bool

esCapicua x = x' == reverse x'

where x' = show x

-- Solución de ejercicio 2

inverso :: Integer -> Integer

inverso = read . reverse . show

-- Solución de ejercicio 3

siguiente :: Integer -> Integer

siguiente x = x + inverso x

-- Solución de ejercicio 4

busquedaDeCapicua :: Integer -> [Integer]

busquedaDeCapicua x | esCapicua x = [x]

| otherwise = x : busquedaDeCapicua (siguiente x)

-- Solución de ejercicio 5

capicuaFinal :: Integer -> Integer

capicuaFinal x = last (busquedaDeCapicua x)

-- Solución de ejercicio 6

orden :: Integer -> Integer

orden x | esCapicua x = 0

| otherwise = 1 + orden (siguiente x)

-- Solución de ejercicio 7

ordenMayor :: Integer -> Integer -> Bool

ordenMayor x n | esCapicua x = n == 0

| n <= 0 = True

| otherwise = ordenMayor (siguiente x) (n-1)

-- Solución de ejercicio 8

ordenEntre :: Integer -> Integer -> [Integer]

ordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]

-- Solución de ejercicio 9

menorDeOrdenMayor :: Integer -> Integer

menorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]

-- Solución de ejercicio 10

menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]

menoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]

-- Solución de ejercicio 11

-- La conjetura es que para n mayor que 1, la última cifra de

-- (menorDeOrdenMayor n) es 9.

-- Solución de ejercicio 12

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

-- La conjetura es

prop_menorDeOrdenMayor :: Integer -> Property

prop_menorDeOrdenMayor n =

n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9

-- La comprobación es

-- λ> quickCheck prop_menorDeOrdenMayor

-- *** Failed! Falsifiable (after 22 tests and 2 shrinks):

-- 25

-- Se puede comprobar que 25 es un contraejemplo,

-- λ> menorDeOrdenMayor 25

-- 196

-- Solución de ejercicio 13

-- El cálculo es

-- λ> menoresdDeOrdenMayor 50

-- [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),

-- (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),

-- (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),

-- (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),

-- (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),

-- (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),

-- (47,196),(48,196),(49,196),(50,196)]

-- Solución de ejercicio 14

-- La conjetura es que el orden de 196 es infinito y, por tanto,

-- 196 es un número del Lychrel.

-- Solución de ejercicio 15

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

-- La propiedad es

prop_ordenDe196 :: Integer -> Bool

prop_ordenDe196 n =

ordenMayor 196 n

-- La comprobación es

-- λ> quickCheck prop_ordenDe196

-- +++ OK, passed 100 tests.

Soluciones en Python

from itertools import islice
from sys import setrecursionlimit
from typing import Generator, Iterator

from hypothesis import given, settings
from hypothesis import strategies as st

setrecursionlimit(10**6)

# Solución del ejercicio 1
def esCapicua(x: int) -> bool:
    return x == int(str(x)[::-1])

# Solución del ejercicio 2
def inverso(x: int) -> int:
    return int(str(x)[::-1])

# Solución del ejercicio 3
def siguiente(x: int) -> int:
    return x + inverso(x)

# Solución del ejercicio 4
def busquedaDeCapicua(x: int) -> list[int]:
    if esCapicua(x):
        return [x]
    return [x] + busquedaDeCapicua(siguiente(x))

# Solución del ejercicio 5
def capicuaFinal(x: int) -> int:
    return busquedaDeCapicua(x)[-1]

# Solución del ejercicio 6
def orden(x: int) -> int:
    if esCapicua(x):
        return 0
    return 1 + orden(siguiente(x))

# Solución del ejercicio 7
def ordenMayor(x: int, n: int) -> bool:
    if esCapicua(x):
        return n == 0
    if n <= 0:
        return True
    return ordenMayor(siguiente(x), n - 1)

# Solución del ejercicio 8
# ========================

# naturales es el generador de los números naturales positivos, Por
# ejemplo,
#    >>> list(islice(naturales(), 5))
#    [1, 2, 3, 4, 5]
def naturales() -> Iterator[int]:
    i = 1
    while True:
        yield i
        i += 1

def ordenEntre(m: int, n: int) -> Generator[int, None, None]:
    return (x for x in naturales()
            if ordenMayor(x, m) and not ordenMayor(x, n))

# Solución del ejercicio 9
def menorDeOrdenMayor(n: int) -> int:
    return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0]

# Solución del ejercicio 10
def menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]:
    return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)]

# Solución del ejercicio 11
# La conjetura es que para n mayor que 1, la última cifra de
# menorDeOrdenMayor(n) es 9.

# Solución del ejercicio 12
# =========================

# La conjetura es
# @given(st.integers(min_value=2, max_value=200))
# def test_menorDeOrdenMayor(n: int) -> None:
#     assert menorDeOrdenMayor(n) % 10 == 9

# La comprobación es
#    src> poetry run pytest -q numeros_de_Lychrel.py
#    E       assert (196 % 10) == 9
#    E        +  where 196 = menorDeOrdenMayor(25)
#    E       Falsifying example: test_menorDeOrdenMayor(
#    E           n=25,
#    E       )

# Se puede comprobar que 25 es un contraejemplo,
#    >>> menorDeOrdenMayor(25)
#    196

# Solución del ejercicio 13
# El cálculo es
#    λ> menoresdDeOrdenMayor 50
#    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
#     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
#     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
#     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
#     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
#     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
#     (47,196),(48,196),(49,196),(50,196)]

# Solución del ejercicio 14
# El orden de 196 es infinito y, por tanto, 196 es un número
# de Lychrel.


# Solución del ejercicio 15
# =========================

# La propiedad es
@settings(deadline=None)
@given(st.integers(min_value=2, max_value=5000))
def test_ordenDe196(n: int) -> None:
    assert ordenMayor(196, n)

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

from itertools import islice

from sys import setrecursionlimit

from typing import Generator, Iterator

from hypothesis import given, settings

from hypothesis import strategies as st

setrecursionlimit(10**6)

# Solución del ejercicio 1

def esCapicua(x: int) -> bool:

return x == int(str(x)[::-1])

# Solución del ejercicio 2

def inverso(x: int) -> int:

return int(str(x)[::-1])

# Solución del ejercicio 3

def siguiente(x: int) -> int:

return x + inverso(x)

# Solución del ejercicio 4

def busquedaDeCapicua(x: int) -> list[int]:

if esCapicua(x):

return [x]

return [x] + busquedaDeCapicua(siguiente(x))

# Solución del ejercicio 5

def capicuaFinal(x: int) -> int:

return busquedaDeCapicua(x)[-1]

# Solución del ejercicio 6

def orden(x: int) -> int:

if esCapicua(x):

return 0

return 1 + orden(siguiente(x))

# Solución del ejercicio 7

def ordenMayor(x: int, n: int) -> bool:

if esCapicua(x):

return n == 0

if n <= 0:

return True

return ordenMayor(siguiente(x), n - 1)

# Solución del ejercicio 8

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

# naturales es el generador de los números naturales positivos, Por

# ejemplo,

# >>> list(islice(naturales(), 5))

# [1, 2, 3, 4, 5]

def naturales() -> Iterator[int]:

i = 1

while True:

yield i

i += 1

def ordenEntre(m: int, n: int) -> Generator[int, None, None]:

return (x for x in naturales()

if ordenMayor(x, m) and not ordenMayor(x, n))

# Solución del ejercicio 9

def menorDeOrdenMayor(n: int) -> int:

return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0]

# Solución del ejercicio 10

def menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]:

return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)]

# Solución del ejercicio 11

# La conjetura es que para n mayor que 1, la última cifra de

# menorDeOrdenMayor(n) es 9.

# Solución del ejercicio 12

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

# La conjetura es

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

# def test_menorDeOrdenMayor(n: int) -> None:

# assert menorDeOrdenMayor(n) % 10 == 9

# La comprobación es

# src> poetry run pytest -q numeros_de_Lychrel.py

# E assert (196 % 10) == 9

# E + where 196 = menorDeOrdenMayor(25)

# E Falsifying example: test_menorDeOrdenMayor(

# E n=25,

# E )

# Se puede comprobar que 25 es un contraejemplo,

# >>> menorDeOrdenMayor(25)

# 196

# Solución del ejercicio 13

# El cálculo es

# λ> menoresdDeOrdenMayor 50

# [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),

# (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),

# (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),

# (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),

# (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),

# (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),

# (47,196),(48,196),(49,196),(50,196)]

# Solución del ejercicio 14

# El orden de 196 es infinito y, por tanto, 196 es un número

# de Lychrel.

# Solución del ejercicio 15

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

# La propiedad es

@settings(deadline=None)

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

def test_ordenDe196(n: int) -> None:

assert ordenMayor(196, n)

# La comprobación es

# src> poetry run pytest -q numeros_de_Lychrel.py

# 1 passed in 7.74s

El algoritmo de Luhn

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

El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.

El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.

Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.

A los números válidos, se les llama números de Luhn.

Definir las siguientes funciones:

   digitosInv    :: Integer -> [Integer]
   doblePosImpar :: [Integer] -> [Integer]
   sumaDigitos   :: [Integer] -> Integer
   ultimoDigito  :: Integer -> Integer
   luhn          :: Integer -> Bool

digitosInv :: Integer -> [Integer]

doblePosImpar :: [Integer] -> [Integer]

sumaDigitos :: [Integer] -> Integer

ultimoDigito :: Integer -> Integer

luhn :: Integer -> Bool

tales que

digitosInv n es la lista de los dígitos del número n, en orden inverso. Por ejemplo,

     digitosInv 320274  ==  [4,7,2,0,2,3]

1	digitosInv 320274 == [4,7,2,0,2,3]

doblePosImpar ns es la lista obtenida doblando los elementos de ns en las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,

     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]
     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]

1 2	doblePosImpar [4,9,5,5] == [4,18,5,10] doblePosImpar [4,9,5,5,7] == [4,18,5,10,7]

sumaDigitos ns es la suma de los dígitos de ns. Por ejemplo,

     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =
                             = 19

1 2	sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 = = 19

ultimoDigito n es el último dígito de n. Por ejemplo,

     ultimoDigito 123 == 3
     ultimoDigito   0 == 0

1 2	ultimoDigito 123 == 3 ultimoDigito 0 == 0

luhn n se verifica si n es un número de Luhn. Por ejemplo,

     luhn 5594589764218858  ==  True
     luhn 1234567898765432  ==  False

1 2	luhn 5594589764218858 == True luhn 1234567898765432 == False

Soluciones

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

Soluciones en Haskell

-- Definición de digitosInv
-- ========================

digitosInv :: Integer -> [Integer]
digitosInv n = [read [x] | x <- reverse (show n)]

-- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
-- se presentan otras definiciones.

-- Definiciones de doblePosImpar
-- =============================

-- 1ª definición
doblePosImpar :: [Integer] -> [Integer]
doblePosImpar []       = []
doblePosImpar [x]      = [x]
doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs

-- 2ª definición
doblePosImpar2 :: [Integer] -> [Integer]
doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs
doblePosImpar2 xs       = xs

-- 3ª definición
doblePosImpar3 :: [Integer] -> [Integer]
doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]
  where f n x | odd n     = 2*x
              | otherwise = x

-- Definiciones de sumaDigitos
-- ===========================

sumaDigitos :: [Integer] -> Integer
sumaDigitos ns = sum [sum (digitosInv n) | n <- ns]

-- Nota: En el ejercicio "Suma de los dígitos de un número"
-- https://bit.ly/3U4u7WR se presentan otras definiciones.

-- Definición de ultimoDigito
-- ==========================

ultimoDigito :: Integer -> Integer
ultimoDigito n = n `rem` 10

-- Definiciones de luhn
-- ====================

-- 1ª definición
luhn1 :: Integer -> Bool
luhn1 n =
  ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0

-- 2ª definición
luhn2 :: Integer -> Bool
luhn2 =
  (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv

-- Definición de digitosInv

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

digitosInv :: Integer -> [Integer]

digitosInv n = [read [x] | x <- reverse (show n)]

-- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

-- se presentan otras definiciones.

-- Definiciones de doblePosImpar

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

-- 1ª definición

doblePosImpar :: [Integer] -> [Integer]

doblePosImpar [] = []

doblePosImpar [x] = [x]

doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs

-- 2ª definición

doblePosImpar2 :: [Integer] -> [Integer]

doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs

doblePosImpar2 xs = xs

-- 3ª definición

doblePosImpar3 :: [Integer] -> [Integer]

doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]

where f n x | odd n = 2*x

| otherwise = x

-- Definiciones de sumaDigitos

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

sumaDigitos :: [Integer] -> Integer

sumaDigitos ns = sum [sum (digitosInv n) | n <- ns]

-- Nota: En el ejercicio "Suma de los dígitos de un número"

-- https://bit.ly/3U4u7WR se presentan otras definiciones.

-- Definición de ultimoDigito

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

ultimoDigito :: Integer -> Integer

ultimoDigito n = n `rem` 10

-- Definiciones de luhn

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

-- 1ª definición

luhn1 :: Integer -> Bool

luhn1 n =

ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0

-- 2ª definición

luhn2 :: Integer -> Bool

luhn2 =

(==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv

Soluciones en Python

# Definición de digitosInv
# ========================

def digitosInv(n: int) -> list[int]:
    return [int(x) for x in reversed(str(n))]

# Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
# se presentan otras definiciones.

# Definiciones de doblePosImpar
# =============================

# 1ª definición
def doblePosImpar(xs: list[int]) -> list[int]:
    if len(xs) <= 1:
        return xs
    return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])

# 2ª definición
def doblePosImpar2(xs: list[int]) -> list[int]:
    def f(n: int, x: int) -> int:
        if n % 2 == 1:
            return 2 * x
        return x
    return [f(n, x) for (n, x) in enumerate(xs)]

# Definiciones de sumaDigitos
# ===========================

def sumaDigitos(ns: list[int]) -> int:
    return sum((sum(digitosInv(n)) for n in ns))

# Nota: En el ejercicio "Suma de los dígitos de un número"
# https://bit.ly/3U4u7WR se presentan otras definiciones.

# Definición de ultimoDigito
# ==========================

def ultimoDigito(n: int) -> int:
    return n % 10

# Definiciones de luhn
# ====================

def luhn(n: int) -> bool:
    return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0

# Definición de digitosInv

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

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

return [int(x) for x in reversed(str(n))]

# Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T

# se presentan otras definiciones.

# Definiciones de doblePosImpar

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

# 1ª definición

def doblePosImpar(xs: list[int]) -> list[int]:

if len(xs) <= 1:

return xs

return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])

# 2ª definición

def doblePosImpar2(xs: list[int]) -> list[int]:

def f(n: int, x: int) -> int:

if n % 2 == 1:

return 2 * x

return x

return [f(n, x) for (n, x) in enumerate(xs)]

# Definiciones de sumaDigitos

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

def sumaDigitos(ns: list[int]) -> int:

return sum((sum(digitosInv(n)) for n in ns))

# Nota: En el ejercicio "Suma de los dígitos de un número"

# https://bit.ly/3U4u7WR se presentan otras definiciones.

# Definición de ultimoDigito

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

def ultimoDigito(n: int) -> int:

return n % 10

# Definiciones de luhn

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

def luhn(n: int) -> bool:

return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0

Subconjuntos de un conjunto

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

Definir la función

   subconjuntos :: [a] -> [[a]]

1	subconjuntos :: [a] -> [[a]]

tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,

   λ> subconjuntos [2,3,4]
   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
   λ> subconjuntos [1,2,3,4]
   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]

λ> subconjuntos [2,3,4]

[[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]

λ> subconjuntos [1,2,3,4]

[[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],

[2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []]

Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.

Soluciones

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

Soluciones en Haskell

import Data.List (sort, subsequences)
import Test.QuickCheck

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

subconjuntos1 :: [a] -> [[a]]
subconjuntos1 []     = [[]]
subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub
  where sub = subconjuntos1 xs

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

subconjuntos2 :: [a] -> [[a]]
subconjuntos2 []     = [[]]
subconjuntos2 (x:xs) = map (x:) sub ++ sub
  where sub = subconjuntos2 xs

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

subconjuntos3 :: [a] -> [[a]]
subconjuntos3 = subsequences

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

-- La propiedad es
prop_subconjuntos :: [Int] -> Bool
prop_subconjuntos xs =
  all (== sort (subconjuntos1 xs))
      [sort (subconjuntos2 xs),
       sort (subconjuntos3 xs)]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> length (subconjuntos1 [1..23])
--    8388608
--    (2.05 secs, 1,476,991,840 bytes)
--    λ> length (subconjuntos2 [1..23])
--    8388608
--    (0.87 secs, 1,208,555,312 bytes)
--    λ> length (subconjuntos3 [1..23])
--    8388608
--    (0.09 secs, 873,006,608 bytes)

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

-- La propiedad es
prop_length_subconjuntos :: [Int] -> Bool
prop_length_subconjuntos xs =
  length (subconjuntos1 xs) == 2 ^ length xs

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos
--    +++ OK, passed 100 tests.

import Data.List (sort, subsequences)

import Test.QuickCheck

-- 1ª solución

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

subconjuntos1 :: [a] -> [[a]]

subconjuntos1 [] = [[]]

subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub

where sub = subconjuntos1 xs

-- 2ª solución

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

subconjuntos2 :: [a] -> [[a]]

subconjuntos2 [] = [[]]

subconjuntos2 (x:xs) = map (x:) sub ++ sub

where sub = subconjuntos2 xs

-- 3ª solución

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

subconjuntos3 :: [a] -> [[a]]

subconjuntos3 = subsequences

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subconjuntos :: [Int] -> Bool

prop_subconjuntos xs =

all (== sort (subconjuntos1 xs))

[sort (subconjuntos2 xs),

sort (subconjuntos3 xs)]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (subconjuntos1 [1..23])

-- 8388608

-- (2.05 secs, 1,476,991,840 bytes)

-- λ> length (subconjuntos2 [1..23])

-- 8388608

-- (0.87 secs, 1,208,555,312 bytes)

-- λ> length (subconjuntos3 [1..23])

-- 8388608

-- (0.09 secs, 873,006,608 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_length_subconjuntos :: [Int] -> Bool

prop_length_subconjuntos xs =

length (subconjuntos1 xs) == 2 ^ length xs

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos

-- +++ OK, passed 100 tests.

Soluciones en Python

from itertools import combinations
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 sympy import FiniteSet

setrecursionlimit(10**6)

A = TypeVar('A')

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

def subconjuntos1(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return [[xs[0]] + ys for ys in sub] + sub
    return [[]]

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

def subconjuntos2(xs: list[A]) -> list[list[A]]:
    if xs:
        sub = subconjuntos1(xs[1:])
        return list(map((lambda ys: [xs[0]] + ys), sub)) + sub
    return [[]]

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

def subconjuntos3(xs: list[A]) -> list[list[A]]:
    c = FiniteSet(*xs)
    return list(map(list, c.powerset()))

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

def subconjuntos4(xs: list[A]) -> list[list[A]]:
    return [list(ys)
            for r in range(len(xs)+1)
            for ys in combinations(xs, r)]

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

# La propiedad es
@given(st.lists(st.integers(), max_size=5))
def test_subconjuntos(xs: list[int]) -> None:
    ys = list(set(xs))
    r = sorted([sorted(zs) for zs in subconjuntos1(ys)])
    assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r
    assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r

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

# 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('subconjuntos1(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos2(range(14))')
#    0.00 segundos
#    >>> tiempo('subconjuntos3(range(14))')
#    6.01 segundos
#    >>> tiempo('subconjuntos4(range(14))')
#    0.00 segundos
#
#    >>> tiempo('subconjuntos1(range(23))')
#    1.95 segundos
#    >>> tiempo('subconjuntos2(range(23))')
#    2.27 segundos
#    >>> tiempo('subconjuntos4(range(23))')
#    1.62 segundos

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

# La propiedad es
@given(st.lists(st.integers(), max_size=7))
def test_length_subconjuntos(xs: list[int]) -> None:
    assert len(subconjuntos1(xs)) == 2 ** len(xs)

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

from itertools import combinations

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 sympy import FiniteSet

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

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

if xs:

sub = subconjuntos1(xs[1:])

return [[xs[0]] + ys for ys in sub] + sub

return [[]]

# 2ª solución

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

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

if xs:

sub = subconjuntos1(xs[1:])

return list(map((lambda ys: [xs[0]] + ys), sub)) + sub

return [[]]

# 3ª solución

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

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

c = FiniteSet(*xs)

return list(map(list, c.powerset()))

# 4ª solución

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

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

return [list(ys)

for r in range(len(xs)+1)

for ys in combinations(xs, r)]

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers(), max_size=5))

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

ys = list(set(xs))

r = sorted([sorted(zs) for zs in subconjuntos1(ys)])

assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r

assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r

assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r

# La comprobación es

# src> poetry run pytest -q subconjuntos_de_un_conjunto.py

# 1 passed in 0.89s

# 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('subconjuntos1(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos2(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos3(range(14))')

# 6.01 segundos

# >>> tiempo('subconjuntos4(range(14))')

# 0.00 segundos

# >>> tiempo('subconjuntos1(range(23))')

# 1.95 segundos

# >>> tiempo('subconjuntos2(range(23))')

# 2.27 segundos

# >>> tiempo('subconjuntos4(range(23))')

# 1.62 segundos

# Comprobación de la propiedad

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

# La propiedad es

@given(st.lists(st.integers(), max_size=7))

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

assert len(subconjuntos1(xs)) == 2 ** len(xs)

# La comprobación es

# src> poetry run pytest -q subconjuntos_de_un_conjunto.py

# 2 passed in 0.95s

Producto cartesiano de dos conjuntos

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

Definir la función

   producto :: [a] -> [b] -> [(a,b)]

1	producto :: [a] -> [b] -> [(a,b)]

tal que producto xs ys es el producto cartesiano de xs e ys. Por
ejemplo,

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

1	producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

producto1 :: [a] -> [a] -> [(a,a)]
producto1 xs ys = [(x,y) | x <- xs, y <- ys]

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

producto2 :: [a] -> [a] -> [(a,a)]
producto2 []     _  = []
producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys

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

-- La propiedad es
prop_producto :: [Int] -> [Int] -> Bool
prop_producto xs ys =
  producto1 xs ys `iguales` producto2 xs ys

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,
--    iguales [3,2,3] [2,3]    ==  True
--    iguales [3,2,3] [2,3,2]  ==  True
--    iguales [3,2,3] [2,3,4]  ==  False
--    iguales [2,3] [4,5]      ==  False
iguales :: Ord a => [a] -> [a] -> Bool
iguales xs ys =
  subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs

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

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

-- La comparación es
--    λ> length (producto1 [1..4000] [1..4000])
--    16000000
--    (2.33 secs, 1,537,551,208 bytes)
--    λ> length (producto2 [1..4000] [1..4000])
--    16000000
--    (2.87 secs, 2,434,095,160 bytes)

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

-- La propiedad es
prop_elementos_producto :: [Int] -> [Int] -> Bool
prop_elementos_producto xs ys =
  length (producto1 xs ys) == length xs * length ys

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

import Test.QuickCheck

-- 1ª solución

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

producto1 :: [a] -> [a] -> [(a,a)]

producto1 xs ys = [(x,y) | x <- xs, y <- ys]

-- 2ª solución

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

producto2 :: [a] -> [a] -> [(a,a)]

producto2 [] _ = []

producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_producto :: [Int] -> [Int] -> Bool

prop_producto xs ys =

producto1 xs ys `iguales` producto2 xs ys

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,

-- iguales [3,2,3] [2,3] == True

-- iguales [3,2,3] [2,3,2] == True

-- iguales [3,2,3] [2,3,4] == False

-- iguales [2,3] [4,5] == False

iguales :: Ord a => [a] -> [a] -> Bool

iguales xs ys =

subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por

-- ejemplo,

-- subconjunto [3,2,3] [2,5,3,5] == True

-- subconjunto [3,2,3] [2,5,6,5] == False

subconjunto :: Ord a => [a] -> [a] -> Bool

subconjunto xs ys =

[x | x <- xs, x `elem` ys] == xs

-- La comprobación es

-- λ> quickCheck prop_producto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (producto1 [1..4000] [1..4000])

-- 16000000

-- (2.33 secs, 1,537,551,208 bytes)

-- λ> length (producto2 [1..4000] [1..4000])

-- 16000000

-- (2.87 secs, 2,434,095,160 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_elementos_producto :: [Int] -> [Int] -> Bool

prop_elementos_producto xs ys =

length (producto1 xs ys) == length xs * length ys

-- La comprobación es

-- λ> quickCheck prop_elementos_producto

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

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

setrecursionlimit(10**6)

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

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

def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    return [(x, y) for x in xs for y in ys]

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

def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    if xs:
        return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)
    return []

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

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_producto(xs: list[int], ys: list[int]) -> None:
    assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))

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

# 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('len(producto1(range(0, 1000), range(0, 500)))')
#    0.03 segundos
#    >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')
#    2.58 segundos

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

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_elementos_producto(xs: list[int], ys: list[int]) -> None:
    assert len(producto1(xs, ys)) == len(xs) * len(ys)

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

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

B = TypeVar('B')

# 1ª solución

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

def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:

return [(x, y) for x in xs for y in ys]

# 2ª solución

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

def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:

if xs:

return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)

return []

# Comprobación de equivalencia

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

# La propiedad es

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

st.lists(st.integers()))

def test_producto(xs: list[int], ys: list[int]) -> None:

assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))

# La comprobación es

# src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py

# 1 passed in 0.31s

# 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('len(producto1(range(0, 1000), range(0, 500)))')

# 0.03 segundos

# >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')

# 2.58 segundos

# Comprobación de la propiedad

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

# La propiedad es

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

st.lists(st.integers()))

def test_elementos_producto(xs: list[int], ys: list[int]) -> None:

assert len(producto1(xs, ys)) == len(xs) * len(ys)

# La comprobación es

# src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py

# 2 passed in 0.48s

El código se encuentra en GitHub.

Exponente de la mayor potencia de x que divide a y

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

Definir la función

   mayorExponente :: Integer -> Integer -> Integer

1	mayorExponente :: Integer -> Integer -> Integer

tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,

   mayorExponente 2 8    ==  3
   mayorExponente 2 9    ==  0
   mayorExponente 5 100  ==  2
   mayorExponente 2 60   ==  2

mayorExponente 2 8 == 3

mayorExponente 2 9 == 0

mayorExponente 5 100 == 2

mayorExponente 2 60 == 2

Nota: Se supone que a > 1 y b > 0.

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

mayorExponente1 :: Integer -> Integer -> Integer
mayorExponente1 a b
  | rem b a /= 0 = 0
  | otherwise    = 1 + mayorExponente1 a (b `div` a)

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

mayorExponente2 :: Integer -> Integer -> Integer
mayorExponente2 a b = aux b 0
  where
    aux c r | rem c a /= 0 = r
            | otherwise    = aux (c `div` a) (r + 1)

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

mayorExponente3 :: Integer -> Integer -> Integer
mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]

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

mayorExponente4 :: Integer -> Integer -> Integer
mayorExponente4 a b =
  fst (until (\ (_,c) -> rem c a /= 0)
             (\ (r,c) -> (r+1, c `div` a))
             (0,b))

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

-- La propiedad es
prop_mayorExponente :: Integer -> Integer -> Property
prop_mayorExponente a b =
  a > 1 && b > 0 ==>
  all (== mayorExponente1 a b)
      [mayorExponente2 a b,
       mayorExponente3 a b,
       mayorExponente4 a b]

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

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

-- La comparación es
--    λ> mayorExponente1 2 (2^(5*10^4))
--    50000
--    (0.12 secs, 179,578,424 bytes)
--    λ> mayorExponente2 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,533,376 bytes)
--    λ> mayorExponente3 2 (2^(5*10^4))
--    50000
--    (3.88 secs, 818,319,096 bytes)
--    λ> mayorExponente4 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,133,344 bytes)
--
--    λ> mayorExponente1 2 (2^(3*10^5))
--    300000
--    (2.94 secs, 5,762,199,064 bytes)
--    λ> mayorExponente2 2 (2^(3*10^5))
--    300000
--    (2.91 secs, 5,773,829,624 bytes)
--    λ> mayorExponente4 2 (2^(3*10^5))
--    300000
--    (3.70 secs, 5,771,396,824 bytes)

import Test.QuickCheck

-- 1ª solución

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

mayorExponente1 :: Integer -> Integer -> Integer

mayorExponente1 a b

| rem b a /= 0 = 0

| otherwise = 1 + mayorExponente1 a (b `div` a)

-- 2ª solución

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

mayorExponente2 :: Integer -> Integer -> Integer

mayorExponente2 a b = aux b 0

where

aux c r | rem c a /= 0 = r

| otherwise = aux (c `div` a) (r + 1)

-- 3ª solución

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

mayorExponente3 :: Integer -> Integer -> Integer

mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]

-- 4ª solución

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

mayorExponente4 :: Integer -> Integer -> Integer

mayorExponente4 a b =

fst (until (\ (_,c) -> rem c a /= 0)

(\ (r,c) -> (r+1, c `div` a))

(0,b))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_mayorExponente :: Integer -> Integer -> Property

prop_mayorExponente a b =

a > 1 && b > 0 ==>

all (== mayorExponente1 a b)

[mayorExponente2 a b,

mayorExponente3 a b,

mayorExponente4 a b]

-- La comprobación es

-- λ> quickCheck prop_mayorExponente

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

-- Comparación de eficiencia

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

-- La comparación es

-- λ> mayorExponente1 2 (2^(5*10^4))

-- 50000

-- (0.12 secs, 179,578,424 bytes)

-- λ> mayorExponente2 2 (2^(5*10^4))

-- 50000

-- (0.13 secs, 181,533,376 bytes)

-- λ> mayorExponente3 2 (2^(5*10^4))

-- 50000

-- (3.88 secs, 818,319,096 bytes)

-- λ> mayorExponente4 2 (2^(5*10^4))

-- 50000

-- (0.13 secs, 181,133,344 bytes)

-- λ> mayorExponente1 2 (2^(3*10^5))

-- 300000

-- (2.94 secs, 5,762,199,064 bytes)

-- λ> mayorExponente2 2 (2^(3*10^5))

-- 300000

-- (2.91 secs, 5,773,829,624 bytes)

-- λ> mayorExponente4 2 (2^(3*10^5))

-- 300000

-- (3.70 secs, 5,771,396,824 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from itertools import islice
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Iterator

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

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

def mayorExponente1(a: int, b: int) -> int:
    if b % a != 0:
        return 0
    return 1 + mayorExponente1(a, b // a)

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

def mayorExponente2(a: int, b: int) -> int:
    def aux(c: int, r: int) -> int:
        if c % a != 0:
            return r
        return aux(c // a, r + 1)
    return aux(b, 0)

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

# naturales es el generador de los números naturales, Por ejemplo,
#    >>> list(islice(naturales(), 5))
#    [0, 1, 2, 3, 4]
def naturales() -> Iterator[int]:
    i = 0
    while True:
        yield i
        i += 1

def mayorExponente3(a: int, b: int) -> int:
    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]

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

def mayorExponente4(a: int, b: int) -> int:
    r = 0
    while b % a == 0:
        b = b // a
        r = r + 1
    return r

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

def prueba1() -> None:
    for x in range(2, 11):
        for y in range(1, 11):
            print(x, y, mayorExponente4(x, y))


# La propiedad es
@given(st.integers(min_value=2, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mayorExponente(a: int, b: int) -> None:
    r = mayorExponente1(a, b)
    assert mayorExponente2(a, b) == r
    assert mayorExponente3(a, b) == r
    assert mayorExponente4(a, b) == r

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

# 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('mayorExponente1(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')
#    1.81 segundos
#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')
#    0.12 segundos
#
#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')
#    12.19 segundos

from itertools import islice

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import Iterator

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def mayorExponente1(a: int, b: int) -> int:

if b % a != 0:

return 0

return 1 + mayorExponente1(a, b // a)

# 2ª solución

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

def mayorExponente2(a: int, b: int) -> int:

def aux(c: int, r: int) -> int:

if c % a != 0:

return r

return aux(c // a, r + 1)

return aux(b, 0)

# 3ª solución

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

# naturales es el generador de los números naturales, Por ejemplo,

# >>> list(islice(naturales(), 5))

# [0, 1, 2, 3, 4]

def naturales() -> Iterator[int]:

i = 0

while True:

yield i

i += 1

def mayorExponente3(a: int, b: int) -> int:

return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]

# 4ª solución

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

def mayorExponente4(a: int, b: int) -> int:

r = 0

while b % a == 0:

b = b // a

r = r + 1

return r

# Comprobación de equivalencia

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

def prueba1() -> None:

for x in range(2, 11):

for y in range(1, 11):

print(x, y, mayorExponente4(x, y))

# La propiedad es

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

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

def test_mayorExponente(a: int, b: int) -> None:

r = mayorExponente1(a, b)

assert mayorExponente2(a, b) == r

assert mayorExponente3(a, b) == r

assert mayorExponente4(a, b) == r

# La comprobación es

# src> poetry run pytest -q exponente_mayor.py

# 1 passed in 0.16s

# 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('mayorExponente1(2, 2**(2*10**4))')

# 0.13 segundos

# >>> tiempo('mayorExponente2(2, 2**(2*10**4))')

# 0.13 segundos

# >>> tiempo('mayorExponente3(2, 2**(2*10**4))')

# 1.81 segundos

# >>> tiempo('mayorExponente4(2, 2**(2*10**4))')

# 0.12 segundos

# >>> tiempo('mayorExponente4(2, 2**(2*10**5))')

# 12.19 segundos

El código se encuentra en GitHub.

Meses: noviembre 2022

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

El tipo de las fórmulas proposicionales

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

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

El tipo de los árboles binarios

El tipo de las listas

El tipo de los números naturales

El tipo de figuras geométricas

Movimientos en el plano

Máximo de una lista

Aplica según propiedad

Concatenación de una lista de listas

Agrupación de elementos por posición

Elementos consecutivos relacionados

Segmentos cuyos elementos cumplen una propiedad

Reconocimiento de subcadenas

Posiciones de un carácter en una cadena

Mayúsculas iniciales

Poner en mayúscula la primera letra y las restantes en minúsculas

Suma de los dígitos de una cadena

Números de Lychrel

El algoritmo de Luhn

Subconjuntos de un conjunto

Producto cartesiano de dos conjuntos

Exponente de la mayor potencia de x que divide a y

Entradas recientes

Buscar

Correo electrónico