Ir al contenido principal

Árbol de cadenas

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

Una cadena con un conjunto de pares ps es una lista xs de elementos distintos de ps tales que la segunda componente de cada elemento de xs es igual a la primera componente de su siguiente elemento. Por ejemplo, si ps = [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)] entonces [(6,4)], [(8,1),(1,6)] y [(8,1),(1,6),(6,4),(4,9)] son cadenas con ps.

Definir la función

   arbolCadenas :: Eq a => [(a,a)] -> Tree [(a,a)]

tal que (arbolCadenas ps) es el árbol de las cadenas formadas con los elementos de ps. Por ejemplo,

   λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,2),(2,3),(3,1)])))
   []
   |
   +- [(1,2)]
   |  |
   |  `- [(3,1),(1,2)]
   |     |
   |     `- [(2,3),(3,1),(1,2)]
   |
   +- [(2,3)]
   |  |
   |  `- [(1,2),(2,3)]
   |     |
   |     `- [(3,1),(1,2),(2,3)]
   |
   `- [(3,1)]
      |
      `- [(2,3),(3,1)]
         |
         `- [(1,2),(2,3),(3,1)]

   λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)])))
   []
   |
   +- [(1,6)]
   |  |
   |  `- [(8,1),(1,6)]
   |
   +- [(2,5)]
   |
   +- [(3,6)]
   |
   +- [(4,9)]
   |  |
   |  `- [(6,4),(4,9)]
   |     |
   |     +- [(1,6),(6,4),(4,9)]
   |     |  |
   |     |  `- [(8,1),(1,6),(6,4),(4,9)]
   |     |
   |     `- [(3,6),(6,4),(4,9)]
   |
   +- [(6,4)]
   |  |
   |  +- [(1,6),(6,4)]
   |  |  |
   |  |  `- [(8,1),(1,6),(6,4)]
   |  |
   |  `- [(3,6),(6,4)]
   |
   `- [(8,1)]

Soluciones

import Data.Tree (Tree (Node), drawTree)

arbolCadenas :: Eq a => [(a,a)] -> Tree [(a,a)]
arbolCadenas ps = aux []
  where
    aux xs = Node xs (map aux (extensiones xs))
    extensiones [] =
      [[p] | p <- ps]
    extensiones ((x,y):rs) =
      [(a,b):(x,y):rs | (a,b) <- ps,
                        b == x,
                        (a,b) `notElem` ((x,y):rs)]