Menor elemento común en listas infinitas ordenadas en Haskell y en Clojure
El enunciado del problema 108 de 4Clojure es el siguiente
Given any number of sequences, each sorted from smallest to largest,find the smallest number which appears in each sequence. The sequences may be infinite, so be careful to search lazily.
A partir de dicho problema he elaborado las siguientes relaciones de ejercicios en Haskell y Clojure, intentando mantener la analogía entre sus soluciones.
Ejercicios en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import GHC.Exts (sortWith) -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- pertenece :: Ord a => a -> [a] -> Bool -- tal que (pertenece x ys) se verifica si x pertenece a la lista ys, -- donde ys es una lista ordenada de menor a mayor y, posiblemente, -- infinita. Por ejemplo, -- pertenece 6 [0,2..] == True -- pertenece 7 [0,2..] == False -- --------------------------------------------------------------------- pertenece :: Ord a => a -> [a] -> Bool pertenece x [] = False pertenece x (y:ys) | x < y = False | x == y = True | x > y = pertenece x ys -- --------------------------------------------------------------------- -- Ejercicio 2. Definir, por comprensión, la función -- menor :: Ord a => [[a]] -> a -- tal que (menor xss) es el menor elemento común a todas las listas de -- xss, donde las listas de xss son ordenadas (de menor a mayor) y, -- posiblemente, infinitas. Por ejemplo, -- menor [[3,4,5]] == 3 -- menor [[1,2,3,4,5,6,7],[0.5,3/2,4,19]] == 4.0 -- menor [[0..],[4,6..],[2,3,5,7,11,13,28]] == 28 -- --------------------------------------------------------------------- menor :: Ord a => [[a]] -> a menor (xs:xss) = head [x | x <- xs, all (x `pertenece`) xss] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- ordenadasPorPrimero :: Ord a => [[a]] -> [[a]] -- tal que (ordenadasPorPrimero xss) es la lista obtenida ordenando los -- elementos de xss, posiblemente infinitos, por su primer elemento. Por -- ejemplo, -- ghci> ordenadasPorPrimero [[4,6],[2,3,5,7,11,13,28],[0,1,7]] -- [[0,1,7],[2,3,5,7,11,13,28],[4,6]] -- ghci> map head (ordenadasPorPrimero [[4,6..],[2,3,5,7],[0,1..]]) -- [0,2,4] -- --------------------------------------------------------------------- ordenadasPorPrimero :: Ord a => [[a]] -> [[a]] ordenadasPorPrimero xss = sortWith head xss -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- primerosIguales :: Ord a => [[a]] -> a -> Bool -- tal que (primerosIguales yss x) se verifica si todas las listas de -- yss, posiblemente infinitas, tienen como primer elemento x. Por -- ejemplo, -- primerosIguales [[2,4],[2..]] 2 == True -- primerosIguales [[1,2,4],[2..]] 2 == False -- --------------------------------------------------------------------- primerosIguales :: Ord a => [[a]] -> a -> Bool primerosIguales yss x = and [x == y | (y:ys) <- yss] -- --------------------------------------------------------------------- -- Ejercicio 5. Definir, por recursión, la función -- menorR :: Ord a => [[a]] -> a -- tal que (menorR xss) es el menor elemento común a todas las listas de -- xss, donde las listas de xss son ordenadas (de menor a mayor) y, -- posiblemente, infinitas. Por ejemplo, -- menorR [[3,4,5]] == 3 -- menorR [[1,2,3,4,5,6,7],[0.5,3/2,4,19]] == 4.0 -- menorR [[0..],[4,6..],[2,3,5,7,11,13,28]] == 28 -- --------------------------------------------------------------------- menorR :: Ord a => [[a]] -> a menorR xss | primerosIguales zss x = x | otherwise = menorR (ys:zss) where ((x:ys):zss) = ordenadasPorPrimero xss |
Ejercicios en Clojure
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
;;; -------------------------------------------------------------------- ;;; Ejercicio 1. Definir la función 'pertenece' tal que (pertenece x ys) ;;; se verifica si x pertenece a la lista ys, donde ys es una lista ;;; ordenada de menor a mayor y, posiblemente, infinita. Por ejemplo, ;;; (= (pertenece 6 (range)) true) ;;; (= (pertenece 6.5 (range)) false) ;;; -------------------------------------------------------------------- (defn pertenece [x ys] (cond (empty? ys) false (< x (first ys)) false (= x (first ys)) true (> x (first ys)) (pertenece x (rest ys)))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 2. Definir, por comprensión, la función 'menor' tal que ;;; (menor xss) es el menor elemento común a todas las listas de xss, ;;; donde las listas de xss son ordenadas (de menor a mayor) y, ;;; posiblemente, infinitas. Por ejemplo, ;;; (= 3 (menor [[3 4 5]])) ;;; (= 4 (menor [[1 2 3 4 5 6 7] [0.5 3/2 4 19]])) ;;; (= 7 (menor [(range) (range 0 100 7/6) [2 3 5 7 11 13]])) ;;; -------------------------------------------------------------------- (defn menor [xss] (first (for [x (first xss) :when (every? (partial pertenece x) (rest xss))] x))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 3. Definir, por filtrado, la función 'menorF' tal que ;;; (menorF xss) es el menor elemento común a todas las listas de xss, ;;; donde las listas de xss son ordenadas (de menor a mayor) y, ;;; posiblemente, infinitas. Por ejemplo, ;;; (= 3 (menorF [[3 4 5]])) ;;; (= 4 (menorF [[1 2 3 4 5 6 7] [0.5 3/2 4 19]])) ;;; (= 7 (menorF [(range) (range 0 100 7/6) [2 3 5 7 11 13]])) ;;; -------------------------------------------------------------------- (defn menorF [xss] (first (filter (fn [x] (every? (partial pertenece x) (rest xss))) (first xss)))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 4. Definir la función 'ordenadasPorPrimero' tal que ;;; (ordenadasPorPrimero xss) es la lista obtenida ordenando los ;;; elementos de xss, posiblemente infinitos, por su primer ;;; elemento. Por ejemplo, ;;; user=> (ordenadasPorPrimero [[4 6] [2 3 5 7 11 13 28] [0 1 7]]) ;;; ([0 1 7] [2 3 5 7 11 13 28] [4 6]) ;;; user=> (map first (ordenadasPorPrimero [(iterate (partial + 2) 4) ;; [2 3] ;; (range)])) ;;; (0 2 4) ;;; -------------------------------------------------------------------- (defn ordenadasPorPrimero [xss] (sort-by first xss)) ;;; -------------------------------------------------------------------- ;;; Ejercicio 5. Definir la función 'primerosIguales' tal que ;;; (primerosIguales yss x) se verifica si todas las listas de yss, ;;; posiblemente infinitas, tienen como primer elemento x. Por ejemplo, ;;; user=> (primerosIguales [[2 4] (for [x (range)] (+ 2 x))] 2) ;;; true ;;; user=> (primerosIguales [[1 2 4] (for [x (range)] (+ 2 x))] 2) ;;; false ;;; -------------------------------------------------------------------- (defn primerosIguales [yss x] (every? (fn [ys] (= (first ys) x)) yss)) ;;; -------------------------------------------------------------------- ;;; Ejercicio 6. Definir, por recursión, la función 'menorR' tal que ;;; (menorR xss) es el menor elemento común a todas las listas de xss, ;;; donde las listas de xss son ordenadas (de menor a mayor) y, ;;; posiblemente, infinitas. Por ejemplo, ;;; (= 3 (menorR [[3 4 5]])) ;;; (= 4 (menorR [[1 2 3 4 5 6 7] [0.5 3/2 4 19]])) ;;; (= 7 (menorR [(range) (range 0 100 7/6) [2 3 5 7 11 13]])) ;;; -------------------------------------------------------------------- (defn menorR [xss] (let [[[x & ys] & zss] (ordenadasPorPrimero xss)] (if (primerosIguales zss x) x (menorR (conj zss ys))))) ;;; -------------------------------------------------------------------- ;;; Ejercicio 7. Definir, por recursión, la función 'menorO' tal que ;;; (menorO &xs) es el menor elemento común a todas las listas de xs, ;;; donde las listas de xs son ordenadas (de menor a mayor) y, ;;; posiblemente, infinitas. Por ejemplo, ;;; (= 3 (menorO [3 4 5])) ;;; (= 4 (menorO [1 2 3 4 5 6 7] [0.5 3/2 4 19])) ;;; (= 7 (menorO (range) (range 0 100 7/6) [2 3 5 7 11 13])) ;;; -------------------------------------------------------------------- (defn menorO [& xs] (menor xs)) ;;; -------------------------------------------------------------------- ;;; Ejercicio 7. Definir, directamente, la función 'menorD' tal que ;;; (menorD &xs) es el menor elemento común a todas las listas de xs, ;;; donde las listas de xs son ordenadas (de menor a mayor) y, ;;; posiblemente, infinitas. Por ejemplo, ;;; (= 3 (menorD [3 4 5])) ;;; (= 4 (menorD [1 2 3 4 5 6 7] [0.5 3/2 4 19])) ;;; (= 7 (menorD (range) (range 0 100 7/6) [2 3 5 7 11 13])) ;;; -------------------------------------------------------------------- (defn menorD [& xs] (let [[[x & ys] & zss] (sort-by first xs)] (if (apply = (map first xs)) x (apply menorD (conj zss ys))))) |
Nota: La definición de ‘menorD’ está basada en la solución publicada por 0x89 en Github.