CODEWITHSUNDEEP
haskellpathtreebinaryproject
Afonso Bessa
Afonso Bessa

Reputation: 31

Haskell - Rose Trees Paths

I'm doing a small project in Haskell, and I'm having difficulty in creating a function Paths of a "Rose Tree". My Rose Tree has a different point where I can have four possibilities since the beginning.

What I was trying to do was:

data RoseTree a = Start [RoseTree Movimento] | Node a [RoseTree Movimento]
        deriving (Eq, Show)

paths :: RoseTree Movimento -> [[Movimento]]
paths (Start []) = []
paths (Node n []) = [[n]]
paths (Node n ns) = map ((:) n . concat . paths) ns
paths (Start xs) = undefined

PS -> Tree Example :

data Movimento = AndarEsquerda | AndarDireita | Trepar | InterageCaixa 
  deriving (Show, Read, Eq, Ord)

Start [Node AndarEsquerda [Node AndarDireita [Node AndarEsquerda [],Node Trepar []]],Node Trepar [Node AndarDireita [Node AndarDireita []],Node AndarEsquerda [Node AndarEsquerda []]]]

Expected output:

[[AndarEsquerda, AndarDireita, AndarEsquerda],
 [AndarEsquerda, AndarDireita, Trepar],
 [Trepar, AndarDireita, AndarDireita],
 [Trepar, AndarEsquerda, AndarEsquerda]]

Tree Example

Upvotes: 2

Views: 256

Answers (1)

David Lukas
David Lukas

Reputation: 1229

In your code is an undefined right-hand side of expression paths (Start xs). It does not return the desired output if I defined using the expression (paths n) ++ (paths (Start ns)).

Trivial cases [] are OK, but you do not go through the list with (n:ns) recursion to make the trivial ones occur. You iterate using the map function, which is an alternative to recursion.

I use the map function for scrolling to the width and recursion for browsing to the depth of the tree.

paths2 :: RoseTree Movimento -> [[Movimento]]
paths2 (Start []) = []
paths2 (Node m []) = [[m]]
paths2 (Node m (n:ns)) = map ((++) [m]) ((paths2 n) ++ (paths2 (Start ns)))
paths2 (Start (n:ns)) = (paths2 n) ++ (paths2 (Start ns))

Output:

[[AndarEsquerda,AndarDireita,AndarEsquerda],
[AndarEsquerda,AndarDireita,Trepar],
[Trepar,AndarDireita,AndarDireita],
[Trepar,AndarEsquerda,AndarEsquerda]]

Edit: You may like using the (n:ns) from the Start.

paths2 :: RoseTree Movimento -> [[Movimento]]
paths2 (Start []) = []
paths2 (Node m []) = [[m]]
paths2 (Node m ns) = map ((:) m) $ paths2 (Start ns)
paths2 (Start (n:ns)) = paths2 n ++ paths2 (Start ns)

Upvotes: 1

Related Questions