Menu Close

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

El tipo de las fórmulas proposicionales se puede definir por

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

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

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

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

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

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

Definir la función

   interpretaciones :: FProp -> [Interpretacion]

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

   λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   [[('A',False),('B',False)],
    [('A',False),('B',True)],
    [('A',True),('B',False)],
    [('A',True),('B',True)]]
Soluciones en Haskell
import Data.List (nub)
 
data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
type Interpretacion = [(Char, Bool)]
 
interpretaciones :: FProp -> [Interpretacion]
interpretaciones p =
  [zip vs i | i <- interpretacionesVar (length vs)]
  where vs = nub (variables p)
 
-- (interpretacionesVar n) es la lista de las interpretaciones de n
-- variables. Por ejemplo,
--    λ> interpretacionesVar 2
--    [[False,False],
--     [False,True],
--     [True,False],
--     [True,True]]
interpretacionesVar :: Int -> [[Bool]]
interpretacionesVar 0 = [[]]
interpretacionesVar n = map (False:) bss ++ map (True:) bss
  where bss = interpretacionesVar (n-1)
 
-- (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 :: 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 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
 
Interpretacion = list[tuple[str, bool]]
 
# 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')))))
#    ['A', 'B']
#    >>> variables (Impl(Var('A'), Conj(Var('A'), Neg (Var('B')))))
#    ['A', 'A', 'B']
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
 
# interpretacionesVar(n) es la lista de las interpretaciones de n
# variables. Por ejemplo,
#    >>> interpretacionesVar 2
#    [[False, False],
#     [False, True],
#     [True, False],
#     [True, True]]
def interpretacionesVar(n: int) -> list[list[bool]]:
    if n == 0:
        return [[]]
    bss = interpretacionesVar(n-1)
    return [[False] + x for x in bss] + [[True] + x for x in bss]
 
def interpretaciones(f: FProp) -> list[Interpretacion]:
    vs = list(set(variables(f)))
    return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]

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

El tipo de las fórmulas proposicionales se puede definir por

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

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

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

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

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

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

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

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

Definir la función

   valor :: Interpretacion -> FProp -> Bool

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

   λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
   λ> valor [('A',False),('B',False)] p
   True
   λ> valor [('A',True),('B',False)] p
   False
Soluciones en Haskell
data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
type Interpretacion = [(Char, Bool)]
 
valor :: Interpretacion -> FProp -> Bool
valor _ (Const b)  = b
valor i (Var x)    = busca x i
valor i (Neg p)    = not (valor i p)
valor i (Conj p q) = valor i p && valor i q
valor i (Impl p q) = valor i p <= valor i q
 
-- (busca c t) es el valor del primer elemento de la lista de asociación
-- t cuya clave es c. Por ejemplo,
--    busca 2 [(1,'a'),(3,'d'),(2,'c')]  ==  'c'
busca :: Eq c => c -> [(c,v)] -> v
busca c t = head [v | (c',v) <- t, c == c']
Soluciones en Python
from 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
 
Interpretacion = list[tuple[str, bool]]
 
# busca(c, t) es el valor del primer elemento de la lista de asociación
# t cuya clave es c. Por ejemplo,
#    >>> busca('B', [('A', True), ('B', False), ('C', True)])
#    False
def busca(c: str, i: Interpretacion) -> bool:
    return [v for (d, v) in i if d == c][0]
 
def valor(i: Interpretacion, f: FProp) -> bool:
    match f:
        case Const(b):
            return b
        case Var(x):
            return busca(x, i)
        case Neg(p):
            return not valor(i, p)
        case Conj(p, q):
            return valor(i, p) and valor(i, q)
        case Impl(p, q):
            return valor(i, p) <= valor(i, q)
    assert False

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

El tipo de las fórmulas proposicionales se puede definir por

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

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

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

Definir la función

   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"
Soluciones en Haskell
data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
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 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
 
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 los árboles binarios

El árbol binario

        5
       / \
      /   \
     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))

El tipo de los árboles binarios se puede definir por

   data Arbol = Hoja Int
              | Nodo Arbol Int Arbol

Definir las funciones

   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
  • aplana a es la lista obtenida aplanando el árbol a. Por ejemplo,
     aplana ejArbol  ==  [1,3,4,5,6,7,9]
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
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

El tipo de las listas

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

   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

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

   longitud (Cons 4 (Cons 2 (Cons 5 Nil)))  ==  3
Soluciones en Haskell
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

El tipo de los números naturales

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

   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

tales que

  • nat2int n es el número entero correspondiente al número natural n. Por ejemplo,
     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))
  • 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
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)
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

El tipo de figuras geométricas

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

Definir las funciones

   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
  • cuadrado n es el cuadrado de lado n. Por ejemplo,
     area (cuadrado 3)  ==  9.0
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
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)

Movimientos en el plano

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

Definir las siguientes funciones

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

Máximo de una lista

Definir la función

   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"
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)
Soluciones en Python
from abc import abstractmethod
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Any, TypeVar, Protocol
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
A = TypeVar('A', bound="Comparable")
 
class Comparable(Protocol):
    """Para comparar"""
    @abstractmethod
    def __eq__(self, other: Any) -> bool:
        pass
 
    @abstractmethod
    def __lt__(self: A, other: A) -> bool:
        pass
 
    def __gt__(self: A, other: A) -> bool:
        return (not self < other) and self != other
 
    def __le__(self: A, other: A) -> bool:
        return self < other or self == other
 
    def __ge__(self: A, other: A) -> bool:
        return not self < other
 
# 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)
 
# ============================
 
# 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

Definir la función

   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]
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)
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:
    f = lambda x: x + 4
    p = lambda x: 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