{"id":1511,"date":"2011-08-19T10:03:47","date_gmt":"2011-08-19T10:03:47","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1511"},"modified":"2011-08-19T10:05:20","modified_gmt":"2011-08-19T10:05:20","slug":"el-problema-de-la-mayor-subsucesion-creciente-en-haskell-y-en-clojure","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-problema-de-la-mayor-subsucesion-creciente-en-haskell-y-en-clojure\/","title":{"rendered":"El problema de la mayor subsucesi\u00f3n creciente en Haskell y en Clojure"},"content":{"rendered":"

A partir del problema 53 de 4Clojure, titulado Longest Increasing Sub-Seq<\/a>, en el que se pide encontrar la subsucesi\u00f3n creciente m\u00e1s larga de elementos consecutivos de una sucesi\u00f3n dada, he elaborado dos relaciones de ejercicios. Una en Haskell, para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>, y la otra en Clojure, siguiendo el patr\u00f3n de la anterior.
\n<\/p>\n

Ejercicios en Haskell<\/h3>\n
\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List (sort)\r\nimport GHC.Exts (sortWith)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    subsucesiones :: [Integer] -> [[Integer]]\r\n-- tal que (subsucesiones xs) es la lista de las subsucesiones\r\n-- crecientes de elementos consecutivos de xs. Por ejemplo, \r\n--    subsucesiones [1,0,1,2,3,0,4,5]  == [[1],[0,1,2,3],[0,4,5]]\r\n--    subsucesiones [5,6,1,3,2,7]      == [[5,6],[1,3],[2,7]]\r\n--    subsucesiones [2,3,3,4,5]        == [[2,3],[3,4,5]]\r\n--    subsucesiones [7,6,5,4]          == [[7],[6],[5],[4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsubsucesiones :: [Integer] -> [[Integer]]\r\nsubsucesiones []  = []\r\nsubsucesiones [x] = [[x]]\r\nsubsucesiones (x:y:zs)\r\n    | x < y     = (x:us):vss\r\n    | otherwise = [x]:p\r\n    where p@(us:vss) = subsucesiones (y:zs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    ordenadas :: [[Integer]] -> [[Integer]]\r\n-- tal que (ordenadas xss) es la lista de los elementos de xss ordenados\r\n-- de mayor a menor longitud. Por ejemplo,\r\n--    ordenadas [[1],[0,1,2,3],[0,4,5]]  ==  [[0,1,2,3],[0,4,5],[1]]\r\n--    ordenadas [[5,6],[1,3],[2,7]]      ==  [[5,6],[1,3],[2,7]]\r\n--    ordenadas [[2,3],[3,4,5]]          ==  [[3,4,5],[2,3]]\r\n--    ordenadas [[7],[6],[5],[4]]        ==  [[7],[6],[5],[4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nordenadas :: [[Integer]] -> [[Integer]]\r\nordenadas xss = \r\n    [ys | (_,_,ys) <- sort [(- length xs,n,xs) | (n,xs) <- zip [1..] xss]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    masLarga :: [[Integer]] -> [Integer]\r\n-- tal que (masLarga xss) es la primera lista de xss con m\u00e1xima\r\n-- longitud. Por ejemplo,\r\n--    masLarga [[1],[0,1,2,3],[0,4,5]]  ==  [0,1,2,3]\r\n--    masLarga [[5,6],[1,3],[2,7]]      ==  [5,6]\r\n--    masLarga [[2,3],[3,4,5]]          ==  [3,4,5]\r\n--    masLarga [[7],[6],[5],[4]]        ==  [7]\r\n-- ---------------------------------------------------------------------\r\n\r\nmasLarga :: [[Integer]] -> [Integer]\r\nmasLarga = head . ordenadas \r\n\r\n-- Otra definici\u00f3n sin usar 'ordenada' es\r\nmasLarga' xss = head [xs | xs <- xss, length xs == m]\r\n    where m = maximum [length xs | xs <- xss]\r\n\r\n-- Otra definici\u00f3n usando 'sortWith' es\r\nmasLarga'' xss = head (sortWith (\\xs -> -(length xs)) xss)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n \r\n--    mayorSubsucesion :: [Integer] -> [Integer]\r\n-- tal que (mayorSubsucesion xss) es la primera subsucesi\u00f3n de elementos\r\n-- consecutivos de xss creciente y cuya longitud es m\u00e1xima y es  mayor o\r\n-- igual que 2. Por ejemplo, \r\n--    mayorSubsucesion [1,0,1,2,3,0,4,5]  ==  [0,1,2,3]\r\n--    mayorSubsucesion [5,6,1,3,2,7]      ==  [5,6]\r\n--    mayorSubsucesion [2,3,3,4,5]        ==  [3,4,5]\r\n--    mayorSubsucesion [7,6,5,4]          ==  []\r\n-- ---------------------------------------------------------------------\r\n\r\nmayorSubsucesion :: [Integer] -> [Integer]\r\nmayorSubsucesion xss\r\n    | length ys < 2 = []\r\n    | otherwise     = ys\r\n    where ys = masLarga (subsucesiones xss)\r\n<\/pre>\n
Ejercicios en Clojure<\/h3>\n
\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 1. Definir la funci\u00f3n 'subsucesiones' tal que\r\n;;; (subsucesiones xs) es la lista de las subsucesiones crecientes de\r\n;;; elementos consecutivos de xs. Por ejemplo,  \r\n;;;    (= (subsucesiones [1 0 1 2 3 0 4 5]) [[1] [0 1 2 3] [0 4 5]])\r\n;;;    (= (subsucesiones [5 6 1 3 2 7])     [[5 6] [1 3] [2 7]])\r\n;;;    (= (subsucesiones [2 3 3 4 5])       [[2 3] [3 4 5]])\r\n;;;    (= (subsucesiones [7 6 5 4])         [[7] [6] [5] [4]])\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn subsucesiones [xs]\r\n  (cond (empty? xs) xs\r\n        (= (count xs) 1) (list xs)\r\n        true (let [vss (subsucesiones (rest xs))]\r\n               (if (< (first xs) (second xs)) \r\n                 (cons (cons (first xs) (first vss)) (rest vss))\r\n                 (cons (list (first xs)) vss)))))\r\n\r\n;;; Otra definici\u00f3n con patrones es\r\n(defn subsucesiones [xs]\r\n  (cond (= (count xs) 0) ()\r\n        (= (count xs) 1) (list xs)\r\n        true (let [[x y & zs] xs\r\n                   [us & vss :as p] (subsucesiones (rest xs))]\r\n               (if (< x y) \r\n                 (cons (cons x us) vss)\r\n                 (cons (list x) p)))))\r\n                  \r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 2. Definir la funci\u00f3n 'ordenadas' tal que (ordenadas xss)\r\n;;; es la lista de los elementos de xss ordenados de mayor a menor\r\n;;; longitud. Por ejemplo, \r\n;;;    (= (ordenadas [[1] [0 1 2 3] [0 4 5]])  [[0 1 2 3] [0 4 5] [1]])\r\n;;;    (= (ordenadas [[5 6] [1 3] [2 7]])      [[5 6] [1 3] [2 7]])\r\n;;;    (= (ordenadas [[2 3] [3 4 5]])          [[3 4 5] [2 3]])\r\n;;;    (= (ordenadas [[7] [6] [5] [4]])        [[7] [6] [5] [4]])\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn ordenadas [xss]\r\n  (sort-by (fn [xs] (- (count xs))) xss))\r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 3. Definir la funci\u00f3n 'masLarga' tal que (masLarga xss) es\r\n;;; la primera lista de xss con m\u00e1xima longitud. Por ejemplo,\r\n;;;    (= (masLarga [[1] [0 1 2 3] [0 4 5]])  [0 1 2 3])\r\n;;;    (= (masLarga [[5 6] [1 3] [2 7]])      [5 6])\r\n;;;    (= (masLarga [[2 3] [3 4 5]])          [3 4 5])\r\n;;;    (= (masLarga [[7] [6] [5] [4]])        [7])\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn masLarga [xs]\r\n  (first (ordenadas xs))) \r\n\r\n;;; --------------------------------------------------------------------\r\n;;; Ejercicio 4. Definir la funci\u00f3n 'mayorSubsucesion' tal que\r\n;;; (mayorSubsucesion xss) es la primera subsucesi\u00f3n de elementos\r\n;;; consecutivos de xss creciente y cuya longitud es m\u00e1xima y es  mayor\r\n;;; o igual que 2. Por ejemplo, \r\n;;;    (= (mayorSubsucesion [1 0 1 2 3 0 4 5])  [0 1 2 3])\r\n;;;    (= (mayorSubsucesion [5 6 1 3 2 7])      [5 6])\r\n;;;    (= (mayorSubsucesion [2 3 3 4 5])        [3 4 5])\r\n;;;    (= (mayorSubsucesion [7 6 5 4])          [])\r\n;;; --------------------------------------------------------------------\r\n\r\n(defn mayorSubsucesion [xss]\r\n  (let [ys (masLarga (subsucesiones xss))]\r\n    (if (< (count ys) 2) [] ys)))\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
A partir del problema 53 de 4Clojure, titulado Longest Increasing Sub-Seq, en el que se pide encontrar la subsucesi\u00f3n creciente m\u00e1s larga de elementos consecutivos de una sucesi\u00f3n dada, he elaborado dos relaciones de ejercicios. Una en Haskell, para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas, y la otra en Clojure, siguiendo…<\/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\/1511"}],"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=1511"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1511\/revisions"}],"predecessor-version":[{"id":1513,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1511\/revisions\/1513"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1511"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1511"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1511"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}