{"id":5875,"date":"2017-12-15T20:05:16","date_gmt":"2017-12-15T19:05:16","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5875"},"modified":"2017-12-15T20:05:16","modified_gmt":"2017-12-15T19:05:16","slug":"i1m2017-definiciones-de-la-lista-infinita-de-factoriales-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-definiciones-de-la-lista-infinita-de-factoriales-en-haskell\/","title":{"rendered":"I1M2017: Definiciones de la lista infinita de factoriales en Haskell"},"content":{"rendered":"<p>En clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentando el ejercicio 9 de la 10\u00aa relaci\u00f3n en el se compara 5 definiciones de la lista infinita de los factoriales desde el punto de vista de su simplicidad y eficiencia.<\/p>\n<p>Las definiciones y comparaciones estudiadas son las que se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    factoriales1 :: [Integer]\n-- tal que factoriales1 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales1  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales1 :: [Integer]\nfactoriales1 = [factorial n | n <- [0..]]\n\n-- (factorial n) es el factorial de n. Por ejemplo,\n--    factorial 4  ==  24\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.2. Definir, usando zipWith, la funci\u00f3n\n--    factoriales2 :: [Integer]\n-- tal que factoriales2 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales2  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales2 :: [Integer]\nfactoriales2 = 1 : zipWith (*) [1..] factoriales2\n\n-- El c\u00e1lculo es\n--    take 4 factoriales2\n--    = take 4 (1 : zipWith (*) [1..] factoriales2)\n--    = 1 : take 3 (zipWith (*) [1..] factoriales2)\n--    = 1 : take 3 (zipWith (*) [1..] [1|R1])           {R1 es tail factoriales2}\n--    = 1 : take 3 (1 : zipWith (*) [2..] [R1])      \n--    = 1 : 1 : take 2 (zipWith (*) [2..] [1|R2])       {R2 es drop 2 factoriales2}  \n--    = 1 : 1 : take 2 (2 : zipWith (*) [3..] [R2])\n--    = 1 : 1 : 2 : take 1 (zipWith (*) [3..] [2|R3])    {R3 es drop 3 factoriales2}  \n--    = 1 : 1 : 2 : take 1 (6 : zipWith (*) [4..] [R3])  \n--    = 1 : 1 : 2 : 6 : take 0 (zipWith (*) [4..] [R3])  \n--    = 1 : 1 : 2 : 6 : []\n--    = [1, 1, 2, 6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.3. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales1 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales2 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales1 in (sum xs - sum xs)\n--    0\n--    (17.51 secs, 5631214332 bytes)\n--    ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 17382284 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.4. Definir, por recursi\u00f3n, la funci\u00f3n\n--    factoriales3 :: [Integer]\n-- tal que factoriales3 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales3  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales3 :: [Integer]\nfactoriales3 = 1 : aux 1 [1..]\n  where aux x (y:ys) = z : aux z ys\n          where z = x*y\n\n-- El c\u00e1lculo es\n--    take 4 factoriales3\n--    = take 4 (1 : aux 1 [1..])\n--    = 1 : take 3 (aux 1 [1..])\n--    = 1 : take 3 (1 : aux 1 [2..])\n--    = 1 : 1 : take 2 (aux 1 [2..])\n--    = 1 : 1 : take 2 (2 : aux 2 [3..])\n--    = 1 : 1 : 2 : take 1 (aux 2 [3..])\n--    = 1 : 1 : 2 : take 1 (6 : aux 6 [4..])\n--    = 1 : 1 : 2 : 6 : take 0 (aux 6 [4..])\n--    = 1 : 1 : 2 : 6 : []\n--    = [1,1,2,6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.5. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales3 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 17382284 bytes)\n--    ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.6. Definir, usando scanl1, la funci\u00f3n\n--    factoriales4 :: [Integer]\n-- tal que factoriales4 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales4  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales4 :: [Integer]\nfactoriales4 = 1 : scanl1 (*) [1..]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.7. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales4 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n--    ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    0\n--    (0.03 secs, 11965328 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.8. Definir, usando iterate, la funci\u00f3n\n--    factoriales5 :: [Integer]\n-- tal que factoriales5 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales5  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales5 :: [Integer]\nfactoriales5 = map snd (iterate f (1,1)) \n  where f (x,y) = (x+1,x*y)\n\n-- El c\u00e1lculo es\n--    take 4 factoriales5\n--    = take 4 (map snd aux)\n--    = take 4 (map snd (iterate f (1,1)))\n--    = take 4 (map snd [(1,1),(2,1),(3,2),(4,6),...])\n--    = take 4 [1,1,2,6,...]\n--    = [1,1,2,6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.9. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales5 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n--    ghci> let xs = take 3000 factoriales5 in (sum xs - sum xs)\n--    0\n--    (0.03 secs, 11965760 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentando el ejercicio 9 de la 10\u00aa relaci\u00f3n en el se compara 5 definiciones de la lista infinita de los factoriales desde el punto de vista de su simplicidad y eficiencia. Las definiciones y comparaciones estudiadas son las que se muestran a&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[265],"tags":[270,316,194],"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\/5875"}],"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=5875"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5875\/revisions"}],"predecessor-version":[{"id":5876,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5875\/revisions\/5876"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5875"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5875"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5875"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}