Search code examples
listhaskellreverse

How can I reverse a nested list in Haskell

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?

Solution

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