noviembre 2022 – Página 2

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.

Meses: noviembre 2022

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

Entradas recientes

Buscar

Correo electrónico