Home > Software engineering >  How can I reverse a nested list in Haskell
How can I reverse a nested list in Haskell

Time:10-27

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