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)]