Haskell: recursively process lists nested arbitrarily deep

Question

I'm learning Haskell and would like to write functions to recursively process lists nested arbitrarily deep.

For example I'd like to write recurReverse, which in the basis case, acts just like the built in reverse, but when passed a nested list, would reverse all the elements of the sublists recursively as well:

recurReverse [1,2]
>> [2,1]
recurReverse [[1],[2],[3,4]]
>> [[4,3],[2],[1]]
recurReverse [[[1,2]]]
>> [[[2,1]]]

Currently I have the basic reverse down:

rev [] = []
rev (h:t) = rev t ++ [h]

But I need more than this -- in the case when the head h is also a list (as opposed to an atom in the LISP sense), I'd like to be able to reverse h as well and return something like rev t ++ [rev h]. When I try that, I get a compiler error saying something like I can't rev h because rev is of type [t] -> [t] but I'm trying to call it on type t, which makes sense. How can I get around this?

Answer 1

as opposed to an atom in the LISP sense

Well, there is no such thing in Haskell. Any type which you don't know a priori (which you can't, if you're doing recursion over types) could possibly be a list itself. There's no notion of atomicity, of “not-list-being” which you could use as a base case for this recursion.

That is, unless you make the distinction explicit. This can be done quite nicely in Haskell, with GADTs:

data Nest t where
   Egg :: t -> Nest t
   Nest :: [Nest t] -> Nest [t]

nestReverse :: Nest t -> Nest t
nestReverse (Egg x) = Egg x
nestReverse (Nest xs) = Nest . reverse $ map nestReverse xs

If you don't like this... well, there is another way, but it's considered ugly / un–Haskell‑ish.

class Atomeous l where
  recurReverse :: l -> l

instance {-# OVERLAPPABLE #-} Atomeous l where
  recurReverse = id
instance Atomeous l => Atomeous [l] where
  recurReverse = reverse . map recurReverse

Now, recurReverse has your intended behaviour. The first instance is for “atomic” types; because it is marked OVERLAPPABLE the compiler will only use this instance if it can't find “a better one” – which it does precisely for lists; these get the recursive call over all elements.