list - 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

as opposed to an atom in the LISP sense

嗯，Haskell 中没有这样的东西。任何你不知道先验的类型(如果你对类型进行递归，你就不能知道)可能是一个列表本身。没有原子性和“非列表存在”的概念，您可以将其用作此递归的基本情况。

也就是说，除非您明确区分。这可以在 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 风格的。

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编译器只有在找不到“更好的”时才会使用这个实例——它正是为列表做的；这些对所有元素进行递归调用。