Árbol de cadenas
En la librería Data.Tree se definen los árboles y los bosques como sigue
1 2 |
data Tree a = Node a (Forest a) type Forest a = [Tree a] |
Se pueden definir árboles. Por ejemplo,
1 |
ej = Node 3 [Node 5 [Node 9 []], Node 7 []] |
Y se pueden dibujar con la función drawTree. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> 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
1 |
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,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
λ> 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
1 2 3 4 5 6 7 8 9 10 11 12 |
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)] |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>