{"id":3977,"date":"2013-12-30T11:21:37","date_gmt":"2013-12-30T10:21:37","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3977"},"modified":"2013-12-30T18:41:02","modified_gmt":"2013-12-30T17:41:02","slug":"el-problema-del-granjero-la-oveja-y-la-col-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-problema-del-granjero-la-oveja-y-la-col-en-haskell\/","title":{"rendered":"El problema del granjero, la oveja y la col en Haskell"},"content":{"rendered":"

Recientemente, Justin Le ha publicado el art\u00edculo Wolf, goat, cabbage: The list MonadPlus & logic problems<\/a> en el que explica c\u00f3mo se pueden usar las m\u00f3nadas para resolver el problema del granjero, el lobo, la oveja y la col. El enunciado de dicho problema es el siguiente<\/p>\n

\nUn granjero fue al mercado y compr\u00f3 un lobo, una oveja y una col. Para volver a su casa ten\u00eda que cruzar un r\u00edo. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben \u00e9l y una de sus compras. Adem\u00e1s, si el lobo se queda solo con la cabra se la come y si la cabra se queda sola con la col se la come. <\/p>\n

El reto del granjero era cruzar \u00e9l mismo y dejar sus compras a la otra orilla del r\u00edo, dejando cada compra intacta. \u00bfC\u00f3mo lo hizo?\n<\/p><\/blockquote>\n

A partir del art\u00edculo, he elaborado la siguiente relaci\u00f3n de ejercicios (para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> y para la siguiente versi\u00f3n del libro Piensa en Haskell<\/a>). En ella se incluyen soluciones sin usar m\u00f3nadas y con m\u00f3nadas (concretamente, los ejercicios 12, 15 y 17).<\/p>\n

La relaci\u00f3n de ejercicios y sus soluciones es la siguiente
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Control.Monad (guard)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Ejercicios                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir el tipo Posiciones para representar las\r\n-- posiciones en la orilla en la que se puede encontrar la barca: la\r\n-- Izquierda o la Derecha.\r\n-- \r\n-- Hacer que el tipo Movimiento sea mostrable y comparable por igualdad.\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Posicion = Izquierda | Derecha\r\n    deriving (Show, Eq)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir el tipo Personaje para representar los\r\n-- personajes del problema (Granjero, Lobo, Oveja y Col).\r\n--\r\n-- Hacer que el tipo Personaje sea mostrable, comparable por igualdad y\r\n-- enumerable. \r\n-- ---------------------------------------------------------------------\r\n\r\ndata Personaje = Granjero | Lobo | Oveja | Col\r\n    deriving (Show, Eq, Enum)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir el tipo Movimiento para representar los\r\n-- movimientos de cada personaje. Por ejemplo, (Mueve Col) representa\r\n-- que se mueven a la orilla opuesta el granjero con la col y \r\n-- (Mueve Granjero) representa que s\u00f3lo se mueve el granjero.\r\n--\r\n-- Hacer que el tipo Movimiento sea comparable por igualdad.\r\n-- ---------------------------------------------------------------------\r\n\r\nnewtype Movimiento = Mueve Personaje\r\n    deriving Eq\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n de escritura del tipo Movimiento\r\n-- usando las siguientes abreviaturas\r\n--    mG es una abreviatura de (Mueve Granjero) \r\n--    mL es una abreviatura de (Mueve Lobo)     \r\n--    mO es una abreviatura de (Mueve Oveja)    \r\n--    mC es una abreviatura de (Mueve Col)      \r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Show Movimiento where\r\n    show (Mueve Granjero) = \"mG\"\r\n    show (Mueve Lobo)     = \"mL\"\r\n    show (Mueve Oveja)    = \"mO\"\r\n    show (Mueve Col)      = \"mC\"\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir las funciones\r\n--    mG, mL, mO, mC :: Movimiento\r\n-- tales que \r\n--    mG es (Mueve Granjero) \r\n--    mL es (Mueve Lobo)     \r\n--    mO es (Mueve Oveja)    \r\n--    mC es (Mueve Col)      \r\n-- ---------------------------------------------------------------------\r\n\r\nmG, mL, mO, mC :: Movimiento\r\nmG = Mueve Granjero\r\nmL = Mueve Lobo\r\nmO = Mueve Oveja\r\nmC = Mueve Col\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir el tipo Plan como una lista de movimientos. Por\r\n-- ejemplo, \r\n--    ghci> [mC,mG,mO] :: Plan\r\n--    [mC,mG,mO]\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Plan = [Movimiento]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la constante\r\n--    planInicial :: Plan\r\n-- tal que planInicial es el plan inicial, en el que a\u00fan no se ha\r\n-- realizado ning\u00fan movimiento.\r\n-- ---------------------------------------------------------------------\r\n\r\nplanInicial :: Plan\r\nplanInicial = []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    posicionMovimientos :: Int -> Posicion\r\n-- tal que (posicionMovimientos n) es la posici\u00f3n despu\u00e9s de n\r\n-- movimientos, estando inicialmente en la orilla izquieda. Por ejemplo,  \r\n--    posicionMovimientos 3  ==  Derecha\r\n--    posicionMovimientos 4  ==  Izquierda\r\n-- ---------------------------------------------------------------------\r\n\r\nposicionMovimientos :: Int -> Posicion\r\nposicionMovimientos n | even n    = Izquierda\r\n                      | otherwise = Derecha\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    posicion :: Plan -> Personaje -> Posicion\r\n-- tal que (posicion p x) es la posici\u00f3n de x al ejecutarse el plan p. \r\n-- Por ejemplo,\r\n--    ghci> [posicion [] x | x <- [Granjero .. Col]]\r\n--    [Izquierda,Izquierda,Izquierda,Izquierda]\r\n--    ghci> [posicion [mO] x | x <- [Granjero .. Col]]\r\n--    [Derecha,Izquierda,Derecha,Izquierda]\r\n--    ghci> [posicion [mO,mG,mL,mO,mC,mG,mO] x | x <- [Granjero .. Col]]\r\n--    [Derecha,Derecha,Derecha,Derecha]\r\n-- --------------------------------------------------------------------- \r\n\r\nposicion :: Plan -> Personaje -> Posicion\r\nposicion p Granjero = posicionMovimientos (length p)\r\nposicion p x        = posicionMovimientos (length (filter (== Mueve x) p))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    esLegal :: Plan -> Movimiento -> Bool\r\n-- tal que (esLegal p m) se verifica si el movimiento m es legal despu\u00e9s\r\n-- de ejecutar el plan p. Por ejemplo,\r\n--    esLegal [mG,mO] mC  ==  True\r\n--    esLegal [mG,mO] mO  ==  False\r\n-- Nota: Siempre es posible mover al granjero s\u00f3lo y s\u00f3lo es posible\r\n-- mover cualquiera de los otros personajes si se encuentra en la misma\r\n-- orilla que el granjero.\r\n-- ---------------------------------------------------------------------\r\n\r\nesLegal :: Plan -> Movimiento -> Bool\r\nesLegal p (Mueve Granjero) = True\r\nesLegal p (Mueve x)        = posicion p x == posicion p Granjero\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n\r\n--    esRedundante :: Plan -> Movimiento -> Bool\r\n-- tal que (esRedundante p m) se verifica si el movimiento m es\r\n-- redundante; es decir, si m es igual al \u00faltimo movimiento de p. Por\r\n-- ejemplo, \r\n--    esRedundante [mC,mL] mC  ==  True\r\n--    esRedundante [mC,mL] mL  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesRedundante :: Plan -> Movimiento -> Bool\r\nesRedundante []     _ = False\r\nesRedundante (m':_) m = m == m' \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    esSeguro :: Plan -> Bool\r\n-- (esSeguro p) se verifica si el plan es seguro; es decir, si tras el\r\n-- \u00faltimo movimiento ning\u00fan personaje se come a otro. Por ejemplo,\r\n--    esSeguro [mO]  ==  True\r\n--    esSeguro [mL]  ==  False\r\n--    esSeguro [mC]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesSeguro :: Plan -> Bool\r\nesSeguro = not . esInseguro\r\n    where esInseguro p = (pC == pO && pC \/= pG) || \r\n                         (pO == pL && pO \/= pG) \r\n                         where pG = posicion p Granjero\r\n                               pL = posicion p Lobo\r\n                               pO = posicion p Oveja\r\n                               pC = posicion p Col\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--    extensiones :: Plan -> [Plan]\r\n-- tal que (extensiones p) es la lista de las extensiones legales no\r\n-- redundantes del plan p con un nuevo paso. Por ejemplo,\r\n--    ghci> extensiones [mO]\r\n--    [[mG,mO]]\r\n--    ghci> extensiones [mG,mO]\r\n--    [[mL,mG,mO],[mC,mG,mO]]\r\n--    ghci> extensiones [mL,mG,mO]\r\n--    [[mO,mL,mG,mO]]\r\n--    ghci> extensiones [mO,mL,mG,mO]\r\n--    [[mC,mO,mL,mG,mO]]\r\n--    ghci> extensiones [mC,mO,mL,mG,mO]\r\n--    [[mG,mC,mO,mL,mG,mO],[mL,mC,mO,mL,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nextensiones :: Plan -> [Plan]\r\nextensiones p =\r\n    [p' | m <- [mG,mL,mO,mC], \r\n          esLegal p m,\r\n          not (esRedundante p m),\r\n          let p' = m:p,\r\n          esSeguro p']\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir, usado la m\u00f3nada de las listas, la funci\u00f3n\r\n--    extensiones2 :: Plan -> [Plan]\r\n-- tal que extensiones2 es equivalente a extensiones. Por ejemplo,\r\n--    ghci> extensiones2 [mO]\r\n--    [[mG,mO]]\r\n--    ghci> extensiones2 [mG,mO]\r\n--    [[mL,mG,mO],[mC,mG,mO]]\r\n--    ghci> extensiones2 [mL,mG,mO]\r\n--    [[mO,mL,mG,mO]]\r\n--    ghci> extensiones2 [mO,mL,mG,mO]\r\n--    [[mC,mO,mL,mG,mO]]\r\n--    ghci> extensiones2 [mC,mO,mL,mG,mO]\r\n--    [[mG,mC,mO,mL,mG,mO],[mL,mC,mO,mL,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nextensiones2 :: Plan -> [Plan]\r\nextensiones2 p = do\r\n  m <- [mG,mL,mO,mC]\r\n  guard (esLegal p m)\r\n  guard (not (esRedundante p m))\r\n  let p' = m : p\r\n  guard (esSeguro p')\r\n  return p'\r\n\r\n-- La definici\u00f3n anterior se puede escribir, usando los operadores\r\n-- (.) y ($), como sigue\r\nextensiones3 :: Plan -> [Plan]\r\nextensiones3 p = do\r\n  m <- [mG,mL,mO,mC] \r\n  guard $ esLegal p m\r\n  guard . not $ esRedundante p m\r\n  let p' = m : p\r\n  guard $ esSeguro p'\r\n  return p'\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    esSolucion :: Plan -> Bool\r\n-- (esSolucion p) se verifica si p es una soluci\u00f3n; es decir si todos se\r\n-- encuentran en la orilla derecha. Por ejemplo,\r\n--    esSolucion [mO,mG,mL,mO,mC,mG,mO]  ==  True\r\n--    esSolucion [mL,mG,mL,mO,mC,mG,mO]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesSolucion :: Plan -> Bool\r\nesSolucion p = all (== Derecha) posiciones\r\n    where posiciones = map (posicion p) [Granjero .. Col]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    planes :: Int -> [Plan]\r\n-- tal que (planes n) es la lista de planes con n pasos. Por ejemplo,\r\n--    planes 1  ==  [[mO]]\r\n--    planes 2  ==  [[mG,mO]]\r\n--    planes 3  ==  [[mL,mG,mO],[mC,mG,mO]]\r\n--    planes 4  ==  [[mO,mL,mG,mO],[mO,mC,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nplanes :: Int -> [Plan]\r\nplanes 0 = [planInicial]\r\nplanes n = concat [extensiones p | p <- planes (n-1)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir, usando la m\u00f3nada de las listas, la funci\u00f3n\r\n--    planes2 :: Int -> [Plan]\r\n-- tal que planes2 sea equivalente a planes. Por ejemplo,\r\n--    planes2 1  ==  [[mO]]\r\n--    planes2 2  ==  [[mG,mO]]\r\n--    planes2 3  ==  [[mL,mG,mO],[mC,mG,mO]]\r\n--    planes2 4  ==  [[mO,mL,mG,mO],[mO,mC,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nplanes2 :: Int -> [Plan]\r\nplanes2 0 = [planInicial]\r\nplanes2 n = (>>= extensiones) (planes (n-1))\r\n\r\n-- Tambi\u00e9n se puede definir usando iteraci\u00f3n:\r\nplanes3 :: Int -> [Plan]\r\nplanes3 n = iterate (>>= extensiones) [planInicial] !! n \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    soluciones :: Int -> [Plan]\r\n-- tal que (soluciones n) es la lista de soluciones con n pasos. Por\r\n-- ejemplo, \r\n--    ghci> soluciones 7\r\n--    [[mO,mG,mL,mO,mC,mG,mO],[mO,mG,mC,mO,mL,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsoluciones :: Int -> [Plan]\r\nsoluciones n = [reverse p | p <- planes n, esSolucion p]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Definir, usando la m\u00f3nada de las listas, la funci\u00f3n\r\n--    soluciones2 :: Int -> [Plan]\r\n-- tal que soluciones2 sea equivalente a soluciones. Por ejemplo,\r\n--    ghci> soluciones 7\r\n--    [[mO,mG,mL,mO,mC,mG,mO],[mO,mG,mC,mO,mL,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsoluciones2 :: Int -> [Plan]\r\nsoluciones2 n = do\r\n  p <- planes2 n\r\n  guard $ esSolucion p\r\n  return (reverse p)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Definir la funci\u00f3n\r\n--    todasSoluciones :: [Plan]\r\n-- tal que todasSoluciones es la lista de todas las soluciones. Por\r\n-- ejemplo, \r\n--    ghci> take 5 todasSoluciones\r\n--    [[mO,mG,mL,mO,mC,mG,mO],\r\n--     [mO,mG,mC,mO,mL,mG,mO],\r\n--     [mO,mG,mL,mO,mC,mL,mO,mC,mL,mO,mC,mG,mO],\r\n--     [mO,mG,mC,mO,mL,mC,mO,mL,mC,mO,mL,mG,mO],\r\n--     [mO,mG,mL,mO,mC,mL,mO,mC,mL,mO,mC,mL,mO,mC,mL,mO,mC,mG,mO]]\r\n-- ---------------------------------------------------------------------\r\n\r\ntodasSoluciones :: [Plan]\r\ntodasSoluciones = concat [soluciones n | n <- [1..]]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Recientemente, Justin Le ha publicado el art\u00edculo Wolf, goat, cabbage: The list MonadPlus & logic problems en el que explica c\u00f3mo se pueden usar las m\u00f3nadas para resolver el problema del granjero, el lobo, la oveja y la col. El enunciado de dicho problema es el siguiente Un granjero fue al mercado y compr\u00f3 un…<\/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":[5,221],"tags":[270,299],"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\/3977"}],"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=3977"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3977\/revisions"}],"predecessor-version":[{"id":3980,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3977\/revisions\/3980"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}