PFH: La semana en Exercitium (18 de noviembre de 2022)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

1. Reconocimiento de subcadenas
2. Segmentos cuyos elementos cumplen una propiedad
3. Elementos consecutivos relacionados
4. Agrupación de elementos por posición
5. Concatenación de una lista de listas

A continuación se muestran las soluciones.

1. Reconocimiento de subcadenas

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

1.1. 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","</b>
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","</b>

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.2. 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

2. Segmentos cuyos elementos cumplen una propiedad

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

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

2.2. 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

3. Elementos consecutivos relacionados

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

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

3.2. 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

4. Agrupación de elementos por posición

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.

4.1. 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.

4.2. 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

5. Concatenación de una lista de listas

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.

5.1. 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.

5.2. 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.

1. Reconocimiento de subcadenas

2. Segmentos cuyos elementos cumplen una propiedad

3. Elementos consecutivos relacionados

4. Agrupación de elementos por posición

5. Concatenación de una lista de listas

Se puede imprimir o compartir con