{"id":3998,"date":"2014-01-14T17:13:55","date_gmt":"2014-01-14T16:13:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3998"},"modified":"2014-01-17T05:40:17","modified_gmt":"2014-01-17T04:40:17","slug":"i1m2013-codificacion-binaria-y-transmision-de-cadenas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-codificacion-binaria-y-transmision-de-cadenas-en-haskell\/","title":{"rendered":"I1M2013: Codificaci\u00f3n binaria y transmisi\u00f3n de cadenas en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha estudiado, como aplicaci\u00f3n de las funciones de orden superior, la codificaci\u00f3n binaria de cadenas y su transmisi\u00f3n.<\/p>\n<p>El c\u00f3digo correspondiente se muestra a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- Objetivo: Definir una funci\u00f3n que convierta una cadena en una lista\r\n-- de ceros y unos junto con otra funci\u00f3n que realice la conversi\u00f3n\r\n-- opuesta.   \r\n\r\n-- Los n\u00fameros binarios se representan mediante listas de bits en orden\r\n-- inverso. Un bit es cero o uno. Por ejemplo, el n\u00famero 1101 se\r\n-- representa por [1,0,1,1]. \r\n\r\n--  El tipo Bit es el de los bits.\r\ntype Bit = Int  \r\n\r\n-- Cambio de bases\r\n-- ===============\r\n\r\n-- (bin2int x) es el n\u00famero decimal correspondiente al n\u00famero binario\r\n-- x. Por ejemplo, \r\n--    bin2int [1,0,1,1]  ==  13\r\nbin2int :: [Bit] -> Int\r\nbin2int =  foldr (\\x y -> x + 2*y) 0\r\n\r\n-- Puede definirse por recursi\u00f3n\r\nbin2intR :: [Bit] -> Int\r\nbin2intR [] = 0\r\nbin2intR (x:xs) = x + 2 * (bin2intR xs)\r\n\r\n-- Puede definirse por comprensi\u00f3n\r\nbin2intC :: [Bit] -> Int\r\nbin2intC xs = sum [x*2^n | (x,n) <- zip xs [0..]]\r\n\r\n-- (int2bin x) es el n\u00famero binario correspondiente al n\u00famero decimal\r\n-- x. Por ejemplo, \r\n--    int2bin 13  ==  [1,0,1,1]  \r\nint2bin :: Int -> [Bit]\r\nint2bin n | n < 2     = [n]\r\n          | otherwise = n `mod` 2 : int2bin (n `div` 2)\r\n\r\n-- Propiedad: Al pasar un n\u00famero natural a binario con int2bin y el\r\n-- resultado a decimal con bin2int se obtiene el n\u00famero inicial.\r\nprop_int_bin :: Int -> Bool\r\nprop_int_bin x =\r\n    bin2int (int2bin y) == y\r\n    where y = abs x\r\n\r\n-- Comprobaci\u00f3n:\r\n--    > quickCheck prop_int_bin\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Codificaci\u00f3n y descodificaci\u00f3n\r\n-- ==============================\r\n\r\n-- Un octeto es un grupo de ocho bits.\r\n\r\n-- (creaOcteto bs) es el octeto correspondiente a la lista de bits bs;\r\n-- es decir, los 8 primeros elementos de bs si su longitud es mayor o\r\n-- igual que 8 y la lista de 8 elemento a\u00f1adiendo ceros al final de bs\r\n-- en caso contrario. Por ejemplo, \r\n--    creaOcteto [1,0,1,1,0,0,1,1,1,0,0,0]  ==  [1,0,1,1,0,0,1,1]\r\n--    creaOcteto [1,0,1,1]                  ==  [1,0,1,1,0,0,0,0]\r\ncreaOcteto :: [Bit] -> [Bit]\r\ncreaOcteto bs =  take 8 (bs ++ repeat 0)\r\n\r\n-- creaOcteto se puede definir sin usar repeat:\r\ncreaOcteto' :: [Bit] -> [Bit]\r\ncreaOcteto' bs =  take 8 (bs ++ replicate 8 0)\r\n\r\n-- (codifica c) es la codificaci\u00f3n de la cadena c como una lista de bits\r\n-- obtenida convirtiendo cada car\u00e1cter en un n\u00famero Unicode,\r\n-- convirtiendo cada uno de dichos n\u00fameros en un octeto y concatenando\r\n-- los octetos para obtener una lista de bits. Por ejemplo, \r\n--    ghci> codifica \"abc\"\r\n--    [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]\r\ncodifica :: String -> [Bit]\r\ncodifica =  concat . map (creaOcteto . int2bin . ord)\r\n\r\n-- (separaOctetos bs) es la lista obtenida separando la lista de bits bs\r\n-- en listas de 8 elementos. Por ejemplo, \r\n--    ghci> separaOctetos [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0]\r\n--    [[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0]]\r\nseparaOctetos :: [Bit] -> [[Bit]]\r\nseparaOctetos [] = []\r\nseparaOctetos bs =  \r\n    take 8 bs : separaOctetos (drop 8 bs)\r\n\r\n-- (descodifica bs) es la cadena correspondiente a la lista de bits\r\n-- bs. Por ejemplo,   \r\n--    ghci> descodifica [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]\r\n--    \"abc\"\r\ndescodifica :: [Bit] -> String\r\ndescodifica =  map (chr . bin2int) . separaOctetos\r\n\r\n-- Los canales de transmisi\u00f3n pueden representarse mediante funciones\r\n-- que transforman cadenas de bits en cadenas de bits. \r\n\r\n-- (transmite c t) es la cadena obtenida transmitiendo la cadena t a\r\n-- trav\u00e9s del canal c. Por ejemplo, \r\n--    ghci> transmite id \"Texto por canal correcto\"\r\n--    \"Texto por canal correcto\"\r\ntransmite :: ([Bit] -> [Bit]) -> String -> String\r\ntransmite canal =  descodifica . canal . codifica\r\n\r\n-- Propiedad: Al trasmitir cualquier cadena por el canal identidad se\r\n-- obtiene la cadena. \r\nprop_transmite :: String -> Bool\r\nprop_transmite cs =\r\n    transmite id cs == cs\r\n\r\n-- Comprobaci\u00f3n de la correcci\u00f3n:\r\n--    ghci> quickCheck prop_transmite\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha estudiado, como aplicaci\u00f3n de las funciones de orden superior, la codificaci\u00f3n binaria de cadenas y su transmisi\u00f3n. El c\u00f3digo correspondiente se muestra a continuaci\u00f3n<\/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":[222],"tags":[270,300,126],"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\/3998"}],"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=3998"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3998\/revisions"}],"predecessor-version":[{"id":4007,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3998\/revisions\/4007"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3998"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3998"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3998"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}