I am trying to reverse a list similar to (A,B,(C,(D,E)),F)
to return something like (F,((E,D),C),B,A)
in haskell.
I know how to return a single list:
rev :: [a] -> [a]
rev [] = []
rev (x:xs) = (rev xs) [x]
but how would I go about this for nested lists?
CodePudding user response:
A possible implementation is as follows:
data Tree a = Leaf a | Node [Tree a] deriving (Eq, Show)
rev (Leaf x) = Leaf x
rev (Node xs) = Node (go (reverse xs)) where
go ((Leaf y):ys) = Leaf y: go ys
go ((Node y):ys) = rev (Node y): go ys
go [] = []
A short test:
λ> tree = Node [Leaf 'A', Leaf 'B', Node [Leaf 'C', Node [Leaf 'D', Leaf 'E']]]
λ> rev tree
Node [Node [Node [Leaf 'E',Leaf 'D'],Leaf 'C'],Leaf 'B',Leaf 'A']
As Daniel Wagner pointed out, this can be implemented much simpler and more elegant:
rev2 (Leaf x) = Leaf x
rev2 (Node xs) = Node (reverse (map rev2 xs))