{"id":7653,"date":"2022-03-04T07:33:28","date_gmt":"2022-03-04T06:33:28","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7653"},"modified":"2022-03-04T07:36:09","modified_gmt":"2022-03-04T06:36:09","slug":"pfh-cadenas-de-bloques-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-cadenas-de-bloques-en-haskell\/","title":{"rendered":"PFH: Cadenas de bloques en Haskell"},"content":{"rendered":"<p>He a\u00f1adido a la colecci\u00f3n de <a href=\"https:\/\/bit.ly\/3CeabJd\">Ejercicios de programaci\u00f3n funcional con Haskell<\/a> la relaci\u00f3n <a href=\"https:\/\/bit.ly\/3trXIgW\">Cadenas de bloques<\/a> en la que se define el tipo de datos de las cadenas de bloques y se estudia las definiciones de funciones sobre el mismo.<\/p>\n<p>El contenido de la relaci\u00f3n es el siguiente<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es presentar una\n-- modelizaci\u00f3n elemental de las cadenas de bloques y usarla para\n-- presentar los m\u00e9todos generales de definiciones de funciones en\n-- Haskell.\n--\n-- Seg\u00fan la Wikipedia, una [cadena de bloques](https:\/\/bit.ly\/35LzyWh),\n-- en ingl\u00e9s \"blockchain\", es una estructura de datos cuya informaci\u00f3n\n-- se agrupa en bloques a los que se les a\u00f1ade metainformaciones\n-- relativas a otro bloque de la cadena anterior en una l\u00ednea temporal.\n--\n-- El tipo de datos Cadenas representa las dacenas de bloque. Tiene un\n-- argumento que representa la transacci\u00f3n del bloque anterior al\n-- actual. Posee dos constructores:\n-- + BloqueOriginal que es el bloque con que se inicia la cadena y\n-- + Bloque que a partir de una cadena c y una transacci\u00f3n t construye una\n--   nueva cadena a\u00f1adi\u00e9ndole a c un bloque con la transacci\u00f3n t.\n-- Adem\u00e1s, se derivan las clases Eq y Show.\n\ndata Cadena t = BloqueOriginal\n              | Bloque (Cadena t) t\n  deriving (Eq, Show)\n\n-- Para simplificar la notaci\u00f3n, se define el operador (|>) como el\n-- constructor Bloque.\n(|>) :: Cadena t -> t -> Cadena t\n(|>) = Bloque\n\ninfixl 5 |>\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    longitudCadena :: Cadena t -> Int\n-- tal que (longitudCadena c) es la longitud de la cadena c. Por ejemplo,\n--    longitudCadena (BloqueOriginal |>2 |>5 |>2)  ==  3\n-- ---------------------------------------------------------------------\n\nlongitudCadena :: Cadena t -> Int\nlongitudCadena BloqueOriginal = 0\nlongitudCadena (Bloque c _)   = 1 + longitudCadena c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    sumaCadena :: Cadena Int -> Int\n-- tal que (sumaCadena c) es la suma de las transacciones de la cadena\n-- c. Por ejemplo,\n--    sumaCadena (BloqueOriginal |>2 |>5 |>2)  ==  9\n-- ---------------------------------------------------------------------\n\nsumaCadena :: Cadena Int -> Int\nsumaCadena BloqueOriginal = 0\nsumaCadena (Bloque c tx) = tx + sumaCadena c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    maxCadena :: Cadena Int -> Int\n-- tal que (maxCadena c) es la mayor de las transacciones de la cadena\n-- c. Por ejemplo,\n--    maxCadena (BloqueOriginal |>2 |>5 |>2)  ==  5\n-- ---------------------------------------------------------------------\n\nmaxCadena :: Cadena Int -> Int\nmaxCadena BloqueOriginal = 0\nmaxCadena (Bloque c tx) = tx `max` maxCadena c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    cadenaMasLarga :: Cadena t -> Cadena t -> Cadena t\n-- tal que (cadenaMasLarga c d) es la cadena de mayor longitud o la\n-- primera, si las dos tienen la misma longitud. Por ejemplo,\n--    \u03bb> cadenaMasLarga (BloqueOriginal |>7) (BloqueOriginal |>2 |>1)\n--    Bloque (Bloque BloqueOriginal 2) 1\n--    \u03bb> cadenaMasLarga (BloqueOriginal |>2 |>1) (BloqueOriginal |>7)\n--    Bloque (Bloque BloqueOriginal 2) 1\n--    \u03bb> cadenaMasLarga (BloqueOriginal |>2) (BloqueOriginal |>7)\n--    Bloque BloqueOriginal 2\n-- ---------------------------------------------------------------------\n\ncadenaMasLarga :: Cadena t -> Cadena t -> Cadena t\ncadenaMasLarga c d\n  | longitudCadena c >= longitudCadena d = c\n  | otherwise                            = d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Se dice que una cadena es v\u00e1lida si, desde el inicio,\n-- cada transacci\u00f3n es mayor que todas las precedentes.\n--\n-- Definir la funci\u00f3n\n--    cadenaValida :: Cadena Int -> Bool\n-- tal que (cadenaValida c) se verifica si c es v\u00e1lida. Por ejemplo,\n--    cadenaValida (BloqueOriginal |>3 |>6 |>7)  ==  True\n--    cadenaValida (BloqueOriginal |>3 |>3 |>7)  ==  False\n--    cadenaValida (BloqueOriginal |>3 |>2 |>7)  ==  False\n-- ---------------------------------------------------------------------\n\ncadenaValida :: Cadena Int -> Bool\ncadenaValida BloqueOriginal              = True\ncadenaValida (Bloque BloqueOriginal _)   = True\ncadenaValida (Bloque c@(Bloque _ t1) t2) = t2 > t1 && cadenaValida c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    esPrefijoDe :: Eq t => Cadena t -> Cadena t -> Bool\n-- tal que (esPrefijoDe c1 c2) se verifica si c1 es un prefijo de c2 o si\n-- son iguales. Por ejemplo,\n--    \u03bb> (BloqueOriginal |>1 |>3) `esPrefijoDe` (BloqueOriginal |>1 |>3 |>2)\n--    True\n--    \u03bb> (BloqueOriginal |>1 |>3) `esPrefijoDe` (BloqueOriginal |>1 |>2 |>3)\n--    False\n--    \u03bb> (BloqueOriginal |>1 |>3) `esPrefijoDe` (BloqueOriginal |>1 |>3)\n--    True\n-- ---------------------------------------------------------------------\n\nesPrefijoDe :: Eq t => Cadena t -> Cadena t -> Bool\nesPrefijoDe BloqueOriginal BloqueOriginal = True\nesPrefijoDe (Bloque _ _)   BloqueOriginal = False\nesPrefijoDe c              d@(Bloque e _) = c `esPrefijoDe` e || c == d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    sonCompatibles :: Eq t => Cadena t -> Cadena t -> Bool\n-- tal que (sonCompatibles c d) se verifica cuando una es prefijo de la\n-- otra. Por ejemplo,\n--    \u03bb> sonCompatibles (BloqueOriginal |>3) (BloqueOriginal |>3 |>2 |>1)\n--    True\n--    \u03bb> sonCompatibles (BloqueOriginal |>3 |>2 |>1) (BloqueOriginal |>3)\n--    True\n--    \u03bb> sonCompatibles (BloqueOriginal |>2 |>1) (BloqueOriginal |>3)\n--    False\n-- ---------------------------------------------------------------------\n\nsonCompatibles :: Eq t => Cadena t -> Cadena t -> Bool\nsonCompatibles c d = c `esPrefijoDe` d || d `esPrefijoDe` c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    prefijoComun :: Eq t => Cadena t -> Cadena t -> Cadena t\n-- tal que (prefijoComun c d) es el mayor prefijo com\u00fan a c y d. Por\n-- ejemplo,\n--    \u03bb> prefijoComun (BloqueOriginal |>3 |>2 |>5) (BloqueOriginal |>3 |>2 |>7)\n--    Bloque (Bloque BloqueOriginal 3) 2\n--    \u03bb> prefijoComun (BloqueOriginal |>3 |>5 |>7) (BloqueOriginal |>3 |>2 |>7)\n--    Bloque BloqueOriginal 3\n--    \u03bb> prefijoComun (BloqueOriginal |>4 |>5 |>7) (BloqueOriginal |>3 |>2 |>7)\n--    BloqueOriginal\n-- ---------------------------------------------------------------------\n\nprefijoComun :: Eq t => Cadena t -> Cadena t -> Cadena t\nprefijoComun BloqueOriginal  _ = BloqueOriginal\nprefijoComun c@(Bloque d _) e\n  | c `esPrefijoDe` e = c\n  | otherwise         = prefijoComun d e\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    tieneBloqueProp :: (t -> Bool) -> Cadena t -> Bool\n-- tal que (tieneBloqueProp p c) se verifica si alguna transacci\u00f3n de c\n-- cumple la propiedad p. Por ejemplo,\n--    tieneBloqueProp even (BloqueOriginal |>3 |>2 |>5)  ==  True\n--    tieneBloqueProp even (BloqueOriginal |>3 |>7 |>5)  ==  False\n-- ---------------------------------------------------------------------\n\ntieneBloqueProp :: (t -> Bool) -> Cadena t -> Bool\ntieneBloqueProp _ BloqueOriginal = False\ntieneBloqueProp p (Bloque c t) = p t || tieneBloqueProp p c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    tieneBloque :: Eq t => t -> Cadena t -> Bool\n-- tal que (tieneBloque t c) se verifica si alguna transacci\u00f3n de c es\n-- igual a t. Por ejemplo,\n--    tieneBloque 7 (BloqueOriginal |>3 |>7 |>5)  ==  True\n--    tieneBloque 8 (BloqueOriginal |>3 |>7 |>5)  ==  False\n-- ---------------------------------------------------------------------\n\ntieneBloque :: Eq t => t -> Cadena t -> Bool\ntieneBloque t = tieneBloqueProp (== t)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Defin9ir la funci\u00f3n\n--    bloquesUnicos :: Eq t => Cadena t -> Bool\n-- tal que (bloquesUnicos c) se verifica si todos los bloque de c son\n-- \u00fanicos (es decir, sus transacciones son distintas). Por ejemplo,\n--    bloquesUnicos (BloqueOriginal |>3 |>7 |>5)  ==  True\n--    bloquesUnicos (BloqueOriginal |>3 |>7 |>3)  ==  False\n-- ---------------------------------------------------------------------\n\nbloquesUnicos :: Eq t => Cadena t -> Bool\nbloquesUnicos BloqueOriginal = True\nbloquesUnicos (Bloque c t) = bloquesUnicos c && not (tieneBloque t c)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    todosBloquesProp :: (t -> Bool) -> Cadena t -> Bool\n-- tal que (todosBloquesProp p c) se verifica si todos los bloques de c\n-- cumplen la propiedad p. Por ejemplo,\n--    todosBloquesProp (== 'x') BloqueOriginal == True\n--    todosBloquesProp even cadena2           == True\n--    todosBloquesProp even cadena3           == False\n-- ---------------------------------------------------------------------\n\ntodosBloquesProp :: (t -> Bool) -> Cadena t -> Bool\ntodosBloquesProp _ BloqueOriginal = True\ntodosBloquesProp p (Bloque c t) = p t && todosBloquesProp p c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    maxCadenas :: [Cadena t] -> Int\n-- tal que (maxCadenas cs) es el m\u00e1ximo de las longitudes de las cadenas\n-- de cs. Por ejemplo,\n--    \u03bb> c1 = BloqueOriginal |>3\n--    \u03bb> c2 = BloqueOriginal |>5 |>1\n--    \u03bb> c3 = BloqueOriginal |>2 |>1 |>2\n--    \u03bb> maxCadenas [c1, c2, c3]\n--    3\n-- ---------------------------------------------------------------------\n\nmaxCadenas :: [Cadena t] -> Int\nmaxCadenas []       = 0\nmaxCadenas (c : cs) = longitudCadena c `max` maxCadenas cs\n\n-- Se puede definir con foldr\nmaxCadenas' :: [Cadena t] -> Int\nmaxCadenas' = foldr (max . longitudCadena) 0\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    mayorPrefijoComun :: Eq t => [Cadena t] -> Cadena t\n-- tal que (mayorPrefijoComun c cs) es el mayor prefijo com\u00fan de las\n-- cadenas c y las de cs. Por ejemplo,\n--    \u03bb> c1 = BloqueOriginal |>3 |>5 |>7 |>4\n--    \u03bb> c2 = BloqueOriginal |>3 |>5 |>2\n--    \u03bb> c3 = BloqueOriginal |>5 |>2\n--    \u03bb> mayorPrefijoComun [c1, c2]\n--    Bloque (Bloque BloqueOriginal 3) 5\n--    \u03bb> mayorPrefijoComun [c1, c2, c3]\n--    BloqueOriginal\n-- ---------------------------------------------------------------------\n\nmayorPrefijoComun :: Eq t => [Cadena t] -> Cadena t\nmayorPrefijoComun []       = BloqueOriginal\nmayorPrefijoComun [c]      = c\nmayorPrefijoComun (c : cs) = c `prefijoComun` mayorPrefijoComun cs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Dada una cadena de enteros, se interpreta cada entero\n-- como un cambio del saldo actual. El bloque inicial tiene un saldo de\n-- 0. El saldo final viene dado por sumaCadena.\n--\n-- Definir la funci\u00f3n\n--    balancesCadena :: Cadena Int -> Cadena Int\n-- tal que (balancesCadena c) es la cadena de los saldos intermedios (es\n-- decir, una cadena con la  misma longitud que c, pero cada entrada\n-- debe ser el saldo intermedio de la cadena original en ese punto). Por\n-- ejemplo,\n--    \u03bb> balancesCadena (BloqueOriginal |>2 |>8 |>4)\n--    Bloque (Bloque (Bloque BloqueOriginal 2) 10) 14\n-- ---------------------------------------------------------------------\n\nbalancesCadena :: Cadena Int -> Cadena Int\nbalancesCadena BloqueOriginal = BloqueOriginal\nbalancesCadena (Bloque c t) =\n  case balancesCadena c of\n    BloqueOriginal -> Bloque BloqueOriginal t\n    d@(Bloque _ b) -> Bloque d (b + t)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    cadenaSinSaldosNegativos :: Cadena Int -> Bool\n-- tal que (cadenaSinSaldosNegativos) se verifica si ninnguno de los saldos\n-- intermedios de c es negativo. Por ejemplo,\n--    cadenaSinSaldosNegativos (BloqueOriginal |>2 |>8 |>4)    == True\n--    cadenaSinSaldosNegativos (BloqueOriginal |>2 |>(-1) |>4) == True\n--    cadenaSinSaldosNegativos (BloqueOriginal |>2 |>(-3) |>4) == False\n-- ---------------------------------------------------------------------\n\ncadenaSinSaldosNegativos :: Cadena Int -> Bool\ncadenaSinSaldosNegativos = todosBloquesProp (>= 0) . balancesCadena\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    acortaMientras :: (t -> Bool) -> Cadena t -> Cadena t\n-- tal que (acortaMientras p cs) es la cadena obtenida eliminando los\n-- bloques finales de c que cumplen la propiedad p. Por ejemplo,\n--    \u03bb> acortaMientras even (BloqueOriginal |>2 |>3 |>4 |>6)\n--    Bloque (Bloque BloqueOriginal 2) 3\n--    \u03bb> acortaMientras even (BloqueOriginal |>2 |>8 |>4 |>6)\n--    BloqueOriginal\n--    \u03bb> acortaMientras even (BloqueOriginal |>2 |>8 |>4 |>5)\n--    Bloque (Bloque (Bloque (Bloque BloqueOriginal 2) 8) 4) 5\n-- ---------------------------------------------------------------------\n\nacortaMientras :: (t -> Bool) -> Cadena t -> Cadena t\nacortaMientras _ BloqueOriginal = BloqueOriginal\nacortaMientras p c@(Bloque d t)\n  | p t       = acortaMientras p d\n  | otherwise = c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    construyeCadena :: Int -> Cadena Int\n-- tal que (construyeCadena n) es la cadena con n bloques donde las transacciones\n-- son 1, 2,..., n. Por ejemplo,\n--    \u03bb> construyeCadena 4\n--    Bloque (Bloque (Bloque (Bloque BloqueOriginal 1) 2) 3) 4\n-- ---------------------------------------------------------------------\n\nconstruyeCadena :: Int -> Cadena Int\nconstruyeCadena n\n  | n <= 0    = BloqueOriginal\n  | otherwise = Bloque (construyeCadena (n - 1)) n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    replicaCadena :: Int -> t -> Cadena t\n-- tal que (replicaCadena n t) es la cadena con n bloques cada uno con\n-- la transacci\u00f3n t. Por ejemplo,\n--    \u03bb> replicaCadena 3 7\n--    Bloque (Bloque (Bloque BloqueOriginal 7) 7) 7\n-- ---------------------------------------------------------------------\n\nreplicaCadena :: Int -> t -> Cadena t\nreplicaCadena n t\n  | n <= 0    = BloqueOriginal\n  | otherwise = Bloque (replicaCadena (n - 1) t) t\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Definir la funci\u00f3n\n--    prefijo :: Int -> Cadena t -> Cadena t\n-- tal que (prefijo n c) es la cadena formada por los n primeros\n-- bloques de c. Por ejemplo,\n--    \u03bb> prefijo 2 (BloqueOriginal |> 3 |> 7 |> 5 |> 4)\n--    Bloque (Bloque BloqueOriginal 3) 7\n--    \u03bb> prefijo 5 (BloqueOriginal |> 3 |> 7 |> 5 |> 4)\n--    Bloque (Bloque (Bloque (Bloque BloqueOriginal 3) 7) 5) 4\n--    \u03bb> prefijo (-3) (BloqueOriginal |> 3 |> 7 |> 5 |> 4)\n--    BloqueOriginal\n-- ---------------------------------------------------------------------\n\nprefijo :: Int -> Cadena t -> Cadena t\nprefijo _ BloqueOriginal   = BloqueOriginal\nprefijo n c@(Bloque d _)\n  | n >= longitudCadena c = c\n  | otherwise             = prefijo n d\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Referencias                                                      --\n-- ---------------------------------------------------------------------\n\n-- Esta relaci\u00f3n de ejercicio es una adaptaci\u00f3n de la de Lars Br\u00fcnjes\n-- \"Chain.hs\" https:\/\/bit.ly\/3IHrdBX\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>He a\u00f1adido a la colecci\u00f3n de Ejercicios de programaci\u00f3n funcional con Haskell la relaci\u00f3n Cadenas de bloques en la que se define el tipo de datos de las cadenas de bloques y se estudia las definiciones de funciones sobre el mismo. El contenido de la relaci\u00f3n es el siguiente<\/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":[337],"tags":[270,56],"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\/7653"}],"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=7653"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7653\/revisions"}],"predecessor-version":[{"id":7656,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7653\/revisions\/7656"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7653"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7653"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7653"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}