{"id":1514,"date":"2011-08-26T11:07:33","date_gmt":"2011-08-26T11:07:33","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1514"},"modified":"2011-08-28T05:37:42","modified_gmt":"2011-08-28T05:37:42","slug":"menor-elemento-comun-en-listas-infinitas-ordenadas-en-haskell-y-en-clojure","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/menor-elemento-comun-en-listas-infinitas-ordenadas-en-haskell-y-en-clojure\/","title":{"rendered":"Menor elemento com\u00fan en listas infinitas ordenadas en Haskell y en Clojure"},"content":{"rendered":"<p>El enunciado del <a href=\"https:\/\/4clojure.com\/problem\/108\">problema 108 de 4Clojure<\/a> es el siguiente<\/p>\n<blockquote><p>\nGiven 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.\n<\/p><\/blockquote>\n<p>A partir de dicho problema he elaborado las siguientes relaciones de ejercicios en Haskell y Clojure, intentando mantener la analog\u00eda entre sus soluciones.<br \/>\n<!--more--><\/p>\n<h2> Ejercicios en Haskell <\/h2>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport GHC.Exts (sortWith)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    pertenece :: Ord a => a -> [a] -> Bool\r\n-- tal que (pertenece x ys) se verifica si x pertenece a la lista ys,\r\n-- donde ys es una lista ordenada de menor a mayor y, posiblemente,\r\n-- infinita. Por ejemplo,\r\n--    pertenece 6 [0,2..]  ==  True\r\n--    pertenece 7 [0,2..]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npertenece :: Ord a => a -> [a] -> Bool\r\npertenece x [] = False\r\npertenece x (y:ys) | x < y  = False\r\n                   | x == y = True\r\n                   | x > y  = pertenece x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, por comprensi\u00f3n, la funci\u00f3n\r\n--    menor :: Ord a => [[a]] -> a\r\n-- tal que (menor xss) es el menor elemento com\u00fan a todas las listas de\r\n-- xss, donde las listas de xss son ordenadas (de menor a mayor) y,\r\n-- posiblemente, infinitas. Por ejemplo,\r\n--    menor [[3,4,5]]                           ==  3\r\n--    menor [[1,2,3,4,5,6,7],[0.5,3\/2,4,19]]    ==  4.0\r\n--    menor [[0..],[4,6..],[2,3,5,7,11,13,28]]  ==  28\r\n-- ---------------------------------------------------------------------\r\n\r\nmenor :: Ord a => [[a]] -> a\r\nmenor (xs:xss) = \r\n    head [x | x <- xs, all (x `pertenece`) xss] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    ordenadasPorPrimero :: Ord a => [[a]] -> [[a]]\r\n-- tal que (ordenadasPorPrimero xss) es la lista obtenida ordenando los\r\n-- elementos de xss, posiblemente infinitos, por su primer elemento. Por\r\n-- ejemplo, \r\n--    ghci> ordenadasPorPrimero [[4,6],[2,3,5,7,11,13,28],[0,1,7]]\r\n--    [[0,1,7],[2,3,5,7,11,13,28],[4,6]]\r\n--    ghci> map head (ordenadasPorPrimero [[4,6..],[2,3,5,7],[0,1..]])\r\n--    [0,2,4]\r\n-- ---------------------------------------------------------------------\r\n\r\nordenadasPorPrimero :: Ord a => [[a]] -> [[a]]\r\nordenadasPorPrimero xss =\r\n    sortWith head xss\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    primerosIguales :: Ord a => [[a]] -> a -> Bool\r\n-- tal que (primerosIguales yss x) se verifica si todas las listas de\r\n-- yss, posiblemente infinitas, tienen como primer elemento x. Por\r\n-- ejemplo, \r\n--    primerosIguales [[2,4],[2..]] 2    ==  True\r\n--    primerosIguales [[1,2,4],[2..]] 2  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nprimerosIguales :: Ord a => [[a]] -> a -> Bool\r\nprimerosIguales yss x = \r\n    and [x == y | (y:ys) <- yss]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    menorR :: Ord a => [[a]] -> a\r\n-- tal que (menorR xss) es el menor elemento com\u00fan a todas las listas de\r\n-- xss, donde las listas de xss son ordenadas (de menor a mayor) y,\r\n-- posiblemente, infinitas. Por ejemplo,\r\n--    menorR [[3,4,5]]                           ==  3\r\n--    menorR [[1,2,3,4,5,6,7],[0.5,3\/2,4,19]]    ==  4.0\r\n--    menorR [[0..],[4,6..],[2,3,5,7,11,13,28]]  ==  28\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorR :: Ord a => [[a]] -> a\r\nmenorR xss | primerosIguales zss x = x\r\n           | otherwise             = menorR (ys:zss)\r\n    where ((x:ys):zss) = ordenadasPorPrimero xss\r\n<\/pre>\n<h2> Ejercicios en Clojure <\/h2>\n<pre lang=\"clojure\">\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 1. Definir la funci\u00f3n 'pertenece' tal que (pertenece x ys)\r\n;;; se verifica si x pertenece a la lista ys, donde ys es una lista\r\n;;; ordenada de menor a mayor y, posiblemente, infinita. Por ejemplo,\r\n;;;    (= (pertenece 6 (range)) true)\r\n;;;    (= (pertenece 6.5 (range)) false)\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn pertenece [x ys]\r\n  (cond (empty? ys) false\r\n        (< x (first ys)) false\r\n        (= x (first ys)) true\r\n        (> x (first ys)) (pertenece x (rest ys))))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 2. Definir, por comprensi\u00f3n, la funci\u00f3n 'menor' tal que\r\n;;; (menor xss) es el menor elemento com\u00fan a todas las listas de xss,\r\n;;; donde las listas de xss son ordenadas (de menor a mayor) y, \r\n;;; posiblemente, infinitas. Por ejemplo,\r\n;;;    (= 3 (menor [[3 4 5]]))\r\n;;;    (= 4 (menor [[1 2 3 4 5 6 7] [0.5 3\/2 4 19]]))\r\n;;;    (= 7 (menor [(range) (range 0 100 7\/6) [2 3 5 7 11 13]]))\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn menor [xss]\r\n  (first (for [x (first xss)\r\n               :when (every? (partial pertenece x) (rest xss))]\r\n           x)))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 3. Definir, por filtrado, la funci\u00f3n 'menorF' tal que\r\n;;; (menorF xss) es el menor elemento com\u00fan a todas las listas de xss,\r\n;;; donde las listas de xss son ordenadas (de menor a mayor) y, \r\n;;; posiblemente, infinitas. Por ejemplo,\r\n;;;    (= 3 (menorF [[3 4 5]]))\r\n;;;    (= 4 (menorF [[1 2 3 4 5 6 7] [0.5 3\/2 4 19]]))\r\n;;;    (= 7 (menorF [(range) (range 0 100 7\/6) [2 3 5 7 11 13]]))\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn menorF [xss]\r\n  (first (filter (fn [x] (every? (partial pertenece x) (rest xss)))\r\n                 (first xss))))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 4. Definir la funci\u00f3n 'ordenadasPorPrimero' tal que\r\n;;; (ordenadasPorPrimero xss) es la lista obtenida ordenando los\r\n;;; elementos de xss, posiblemente infinitos, por su primer\r\n;;; elemento. Por ejemplo, \r\n;;;    user=> (ordenadasPorPrimero [[4 6] [2 3 5 7 11 13 28] [0 1 7]])\r\n;;;    ([0 1 7] [2 3 5 7 11 13 28] [4 6])\r\n;;;    user=> (map first (ordenadasPorPrimero [(iterate (partial + 2) 4)\r\n;;                                             [2 3]\r\n;;                                             (range)])) \r\n;;;    (0 2 4)\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn ordenadasPorPrimero [xss]\r\n  (sort-by first xss))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 5. Definir la funci\u00f3n 'primerosIguales' tal que\r\n;;; (primerosIguales yss x) se verifica si todas las listas de yss,\r\n;;; posiblemente infinitas, tienen como primer elemento x. Por ejemplo, \r\n;;;    user=> (primerosIguales [[2 4] (for [x (range)] (+ 2 x))] 2)\r\n;;;    true\r\n;;;    user=> (primerosIguales [[1 2 4] (for [x (range)] (+ 2 x))] 2)\r\n;;;    false\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn primerosIguales [yss x]\r\n  (every? (fn [ys] (= (first ys) x)) yss))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 6. Definir, por recursi\u00f3n, la funci\u00f3n 'menorR' tal que\r\n;;; (menorR xss) es el menor elemento com\u00fan a todas las listas de xss,\r\n;;; donde las listas de xss son ordenadas (de menor a mayor) y,\r\n;;; posiblemente, infinitas. Por ejemplo, \r\n;;;    (= 3 (menorR [[3 4 5]]))\r\n;;;    (= 4 (menorR [[1 2 3 4 5 6 7] [0.5 3\/2 4 19]]))\r\n;;;    (= 7 (menorR [(range) (range 0 100 7\/6) [2 3 5 7 11 13]]))\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn menorR [xss]\r\n  (let [[[x & ys] & zss] (ordenadasPorPrimero xss)]\r\n    (if (primerosIguales zss x)\r\n      x\r\n      (menorR (conj zss ys)))))\r\n      \r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 7. Definir, por recursi\u00f3n, la funci\u00f3n 'menorO' tal que\r\n;;; (menorO &xs) es el menor elemento com\u00fan a todas las listas de xs,\r\n;;; donde las listas de xs son ordenadas (de menor a mayor) y,\r\n;;; posiblemente, infinitas. Por ejemplo, \r\n;;;    (= 3 (menorO [3 4 5]))\r\n;;;    (= 4 (menorO [1 2 3 4 5 6 7] [0.5 3\/2 4 19]))\r\n;;;    (= 7 (menorO (range) (range 0 100 7\/6) [2 3 5 7 11 13]))\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn menorO [& xs]\r\n  (menor xs))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 7. Definir, directamente, la funci\u00f3n 'menorD' tal que\r\n;;; (menorD &xs) es el menor elemento com\u00fan a todas las listas de xs,\r\n;;; donde las listas de xs son ordenadas (de menor a mayor) y,\r\n;;; posiblemente, infinitas. Por ejemplo, \r\n;;;    (= 3 (menorD [3 4 5]))\r\n;;;    (= 4 (menorD [1 2 3 4 5 6 7] [0.5 3\/2 4 19]))\r\n;;;    (= 7 (menorD (range) (range 0 100 7\/6) [2 3 5 7 11 13]))\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn menorD [& xs]\r\n  (let [[[x & ys] & zss] (sort-by first xs)]\r\n    (if (apply = (map first xs))\r\n      x\r\n      (apply menorD (conj zss ys)))))\r\n<\/pre>\n<p><b>Nota<\/b>: La definici\u00f3n de &#8216;menorD&#8217; est\u00e1 basada en la <a href=\"https:\/\/gist.github.com\/1171983\">soluci\u00f3n publicada por 0x89 en Github<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[179,5],"tags":[293,270],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1514"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1514"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1514\/revisions"}],"predecessor-version":[{"id":1523,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1514\/revisions\/1523"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}