Haskell:递归地处理嵌套任意深度的列表

Question

我正在学习Haskell,并希望编写函数来递归处理嵌套任意深度的列表.

例如,我想写recurReverse,在基础情况下,就像内置一样reverse,但是当传递一个嵌套列表时,reverse子列表的所有元素也会递归:

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

目前我有基本的reverse下来:

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

但是我需要的不仅仅是这个 - 在头部h也是一个列表的情况下(与LISP意义上的原子相对),我希望能够做到reverse h并返回类似的东西rev t ++ [rev h].当我尝试这个时,我得到一个编译错误,说我不能,rev h因为rev是类型[t] -> [t]但我试图在类型上调用它t,这是有道理的.我怎么能绕过这个？

Answer 1

而不是LISP意义上的原子

好吧,Haskell没有这样的东西.任何你不知道先验的类型(你不能,如果你正在对类型进行递归)可能是一个列表本身.没有原子性的概念,"not-list-being"你可以用作这种递归的基本情况.

也就是说,除非你明确区分.这可以在Haskell中很好地完成,使用GADT:

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

如果你不喜欢这个......好吧,还有另外一种方法,但它被认为是丑陋的/非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

现在,recurReverse有你想要的行为.第一个例子是"原子"类型; 因为它被标记OVERLAPPABLE为编译器只会使用这个实例,如果它找不到"更好的" - 它正是为列表做的; 这些对所有元素进行递归调用.