我正在学习 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
上调用它,这是有道理的。我该如何解决这个问题?
最佳答案
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
编译器只有在找不到“更好的”时才会使用这个实例——它正是为列表做的;这些对所有元素进行递归调用。
关于list - Haskell:递归处理任意深度嵌套的列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35806922/