CODEWITHSUNDEEP
haskellrecursiontree
Rard
Rard

Reputation: 41

Haskell : How do I reverse a the children of a Tree recursive

I am trying to reverse the children of a Tree in haskell. The Tree looks like this: 

data Tree v e = Node v [(e,Tree v e)]

At the moment I do it with these two functions: 

rev :: Tree v e -> Tree v e
rev (Node v []) = Node v []
rev (Node v xs) =
  let xs' = (rev'(snd (unzip xs)))
  in Node v (zip (fst (unzip xs)) (map rev xs'))


rev' :: [Tree v e] -> [Tree v e]
rev' [] = []
rev' (x:xs) = (rev' xs) ++ [x]

I am not even sure if this works 100%. Is there any way to do it recursive in just one function? I feel like my way is inefficient. I was trying to write a function that looks like this:

revRec :: Tree v e -> Tree v e
revRec (Node v [])     = Node v []
revRec (Node v (x:xs)) = Node v (revRec xs ++ [x])

Obviosuly I can't call revRec with xs since xs a list. I just can't wrap my head around this problem even though I feel like it shoudn't be that hard.

Upvotes: 0

Views: 1278

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120711

Zeroth, clean up your code. You don't need those many parens, and you should avoid duplicate computations. fst and snd on twice the same thing? Meh. Better use pattern matching:

rev :: Tree v e -> Tree v e
rev (Node v xs)
  = let (es, cs) = unzip xs
        xs' = rev' cs
    in Node v $ zip es (map rev xs')

rev' :: [Tree v e] -> [Tree v e]
rev' [] = []
rev' (x:xs) = rev' xs ++ [x]

First note that rev' is not specific to lists of trees, at all! It's just an inefficient implementation of the standard reverse function, which works on any list.

Second, this unzipping/zipping is a bit clumsy. Are you sure this is actually the behaviour you want: right now you're only reversing the list of children, but the order of elements stays the same. If not, then you'd better do it all with one reverse and one map:

rev :: Tree v e -> Tree v e
rev (Node v xs) = Node v . reverse $ map (\(e,c) -> (e, rev c)) xs

or, even nicer,

import Control.Arrow

rev (Node v xs) = Node v . reverse $ map (second rev) xs

Upvotes: 2

Related Questions