duplicaElementos :: [a] -> [a]

duplicaElementos [3,2,5]    ==  [3,3,2,2,5,5]
duplicaElementos "Haskell"  ==  "HHaasskkeellll"

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

duplicaElementos1 :: [a] -> [a]
duplicaElementos1 []     = []
duplicaElementos1 (x:xs) = x : x : duplicaElementos1 xs

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

duplicaElementos2 :: [a] -> [a]
duplicaElementos2 = foldr (\x ys -> x:x:ys) []

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

duplicaElementos3 :: [a] -> [a]
duplicaElementos3 xs = concat [[x,x] | x <- xs]

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

duplicaElementos4 :: [a] -> [a]
duplicaElementos4 xs = concat (map (replicate 2) xs)

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

duplicaElementos5 :: [a] -> [a]
duplicaElementos5 = concatMap (replicate 2)

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

duplicaElementos6 :: [a] -> [a]
duplicaElementos6 = (>>= replicate 2)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> [Int]) -> Spec
specG duplicaElementos = do
  it "e1" $
    duplicaElementos [3,2,5] `shouldBe` [3,3,2,2,5,5]

spec :: Spec
spec = do
  describe "def. 1" $ specG duplicaElementos1
  describe "def. 2" $ specG duplicaElementos2
  describe "def. 3" $ specG duplicaElementos3
  describe "def. 4" $ specG duplicaElementos4
  describe "def. 5" $ specG duplicaElementos5
  describe "def. 6" $ specG duplicaElementos6

-- La verificación es
--    λ> verifica
--
--    6 examples, 0 failures

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_duplicaElementos :: [Int] -> Bool
prop_duplicaElementos xs =
  all (== duplicaElementos1 xs)
      [f xs | f <- [duplicaElementos2,
                    duplicaElementos3,
                    duplicaElementos4,
                    duplicaElementos5,
                    duplicaElementos6]]

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

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

-- La comparación es
--    λ> length (duplicaElementos1 [1..10^7])
--    20000000
--    (3.03 secs, 2,560,602,200 bytes)
--    λ> length (duplicaElementos2 [1..10^7])
--    20000000
--    (2.19 secs, 2,000,602,232 bytes)
--    λ> length (duplicaElementos3 [1..10^7])
--    20000000
--    (2.17 secs, 3,520,602,304 bytes)
--    λ> length (duplicaElementos4 [1..10^7])
--    20000000
--    (0.70 secs, 4,080,602,272 bytes)
--    λ> length (duplicaElementos5 [1..10^7])
--    20000000
--    (0.58 secs, 3,200,602,312 bytes)
--    λ> length (duplicaElementos6 [1..10^7])
--    20000000
--    (0.56 secs, 3,200,602,312 bytes)

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

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

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

def duplicaElementos1(ys: list[A]) -> list[A]:
    if not ys:
        return []
    x, *xs = ys
    return [x, x] + duplicaElementos1(xs)

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

def duplicaElementos2(xs: list[A]) -> list[A]:
    return reduce(lambda ys, x: ys + [x, x], xs, [])

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

def duplicaElementos3(xs: list[A]) -> list[A]:
    return [x for x in xs for _ in range(2)]

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

def duplicaElementos4(xs: list[A]) -> list[A]:
    ys = []
    for x in xs:
        ys.append(x)
        ys.append(x)
    return ys

# Verificación
# ============

def test_duplicaElementos() -> None:
    for duplicaElementos in [duplicaElementos1, duplicaElementos2,
                             duplicaElementos3, duplicaElementos4]:
        assert duplicaElementos([3,2,5]) == [3,3,2,2,5,5]
    print("Verificado")

# La verificación es
#    >>> test_duplicaElementos()
#    Verificado

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.lists(st.integers()))
def test_duplicaElementos_equiv(xs: list[int]) -> None:
    r = duplicaElementos1(xs)
    assert duplicaElementos2(xs) == r
    assert duplicaElementos3(xs) == r
    assert duplicaElementos4(xs) == r

# La comprobación es
#    >>> test_duplicaElementos_equiv()
#    >>>

# 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('duplicaElementos1(range(10**4))')
#    0.59 segundos
#    >>> tiempo('duplicaElementos2(range(10**4))')
#    0.20 segundos
#    >>> tiempo('duplicaElementos3(range(10**4))')
#    0.00 segundos
#    >>> tiempo('duplicaElementos4(range(10**4))')
#    0.00 segundos
#
#    >>> tiempo('duplicaElementos2(range(10**5))')
#    21.69 segundos
#    >>> tiempo('duplicaElementos3(range(10**5))')
#    0.02 segundos
#    >>> tiempo('duplicaElementos4(range(10**5))')
#    0.04 segundos
#
#    >>> tiempo('duplicaElementos3(range(10**7))')
#    1.88 segundos
#    >>> tiempo('duplicaElementos4(range(10**7))')
#    1.03 segundos

(ql:quickload "fiveam" :silent t)

(defpackage :duplicacion-de-cada-elemento
  (:use :cl
        :fiveam))

(in-package :duplicacion-de-cada-elemento)

;;; 1ª solución
;;; ============

(defun duplica-elementos-1 (xs)
  (if (null xs)
      nil
      (cons (first xs) (cons (first xs) (duplica-elementos-1 (rest xs))))))

;;; 2ª solución
;;; ===========

(defun duplica-elementos-2 (xs)
  (reduce (lambda (x ys) (cons x (cons x ys)))
          xs
          :from-end t
          :initial-value '()))

;;; 3ª solución
;;; ===========

(defun duplica-elementos-3 (xs)
  (apply #'append
         (mapcar (lambda (x) (list x x)) xs)))

;;; 4ª solución
;;; ===========

(defun duplica-elementos-4 (xs)
  (reduce #'append
          (mapcar (lambda (x) (list x x)) xs)
          :initial-value '()
          :from-end t))

;;; 5ª solución
;;; ===========

(defun duplica-elementos-5 (xs)
  (mapcan (lambda (x) (list x x)) xs))

;;; 6ª solución
;;; ===========

(defun duplica-elementos-6 (xs)
  (loop for x in xs
        appending (list x x)))

;;; 7ª solución
;;; ===========

(defun duplica-elementos-7 (xs)
  (let ((ys '()))
    (dolist (x xs (reverse ys))
      (setf ys (cons x (cons x ys))))))

;;; Verificación
;;; ============

(test duplica-elementos
  (mapc (lambda (duplica-elementos)
          (is (equal (funcall duplica-elementos '(3 2 5)) '(3 3 2 2 5 5))))
        '(duplica-elementos-1
          duplica-elementos-2
          duplica-elementos-3
          duplica-elementos-4
          duplica-elementos-5
          duplica-elementos-6
          duplica-elementos-7)))

(defun verifica ()
  (run 'duplica-elementos))

;;; La verificación es
;;;    (verifica)
;;;
;;;    Running test DUPLICA-ELEMENTOS ........

;;; Equivalencia de las definiciones
;;; ================================

;;; La propiedad es
(test duplica-elementos-equiv
  (for-all ((xs (gen-list)))
    (let ((ys (duplica-elementos-1 xs)))
      (is (equal ys (duplica-elementos-2 xs)))
      (is (equal ys (duplica-elementos-3 xs)))
      (is (equal ys (duplica-elementos-4 xs)))
      (is (equal ys (duplica-elementos-5 xs)))
      (is (equal ys (duplica-elementos-6 xs)))
      (is (equal ys (duplica-elementos-7 xs))))))

(defun comprueba ()
  (run 'duplica-elementos-equiv))

;;; La comprobación es
;;;    > (comprueba)
;;;
;;;    Running test DUPLICA-ELEMENTOS-EQUIV ...

;;; Comparación de eficiencia
;;; =========================

;;; La comparación es
;;;    > (defvar ejemplo1 (loop for i from 1 to 40000 collect i))
;;;    > (time (length (duplica-elementos-1 ejemplo1)))
;;;    0.003 seconds of real time
;;;    > (time (length (duplica-elementos-2 ejemplo1)))
;;;    0.003 seconds of real time
;;;    > (time (length (duplica-elementos-3 ejemplo1)))
;;;    0.003 seconds of real time
;;;    > (time (length (duplica-elementos-4 ejemplo1)))
;;;    0.006 seconds of real time
;;;    > (time (length (duplica-elementos-5 ejemplo1)))
;;;    0.004 seconds of real time
;;;    > (time (length (duplica-elementos-6 ejemplo1)))
;;;    0.001 seconds of real time
;;;    > (time (length (duplica-elementos-7 ejemplo1)))
;;;    0.007 seconds of real time
;;;
;;;    > (time (length (duplica-elementos-2 (make-list 1000000 :initial-element 0))))
;;;    0.154 seconds of real time
;;;    (time (length (duplica-elementos-4 (make-list 1000000 :initial-element 0))))
;;;    0.168 seconds of real time
;;;    > (time (length (duplica-elementos-5 (make-list 1000000 :initial-element 0))))
;;;    0.146 seconds of real time
;;;    > (time (length (duplica-elementos-6 (make-list 1000000 :initial-element 0))))
;;;    0.075 seconds of real time
;;;    > (time (length (duplica-elementos-7 (make-list 1000000 :initial-element 0))))
;;;    0.099 seconds of real time