哈斯克尔：递归处理嵌套的任意深度名单

我学习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也是一个列表（而不是在T原子他LISP的感觉），我希望能够reverseh以及返回类似rev t ++ [rev h]。当我尝试，我得到一个编译错误，说像我不能rev h因为rev是[t] -> [t]类型，但我想调用它t类型，这是有道理的。我怎样才能解决这个问题？

来源

2016-03-04 Yibo Yang

你需要为列表编写一个类型来编码类型级别的嵌套深度，这样就可以编写一个函数递归，而不是在* list *上，而是在*嵌套深度*。可能最简单的方法是使用类型族。 – user2407038

，而不是一个原子在LISP感

那么，有在Haskell没有这样的事情。任何你不知道先验的类型（你不能，如果你是通过类型递归的话）可能是一个列表本身。没有原子性的概念，“ not-list-being ”，您可以使用它作为此递归的基本情况。

也就是说，除非你做出区分明确。这可以在Haskell很好地进行，并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

如果你不喜欢这个......嗯，还有另一种途径，但它被认为是丑陋/ UN-哈斯克尔十岁上下。

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编译器将只使用这种情况下，如果它不能找到“一个更好的” –它恰恰确实为列表;这些将获得对所有元素的递归调用。

来源

2016-03-04 22:14:43 leftaroundabout

谢谢！那么可以肯定地说，如果我想要能够避开Haskell的类型系统并使用“动态”递归数据结构（例如树），几乎总是需要多态性？ –

根本不是！多态性对于编写泛型代码是超级用户，但您完全可以将递归数据结构单独编写为单形ADT。请注意，Haskell中的树与嵌套列表完全不同。列表明确具有_flat/homogeneous_结构，这与Lisp非常不同。 – leftaroundabout

哈斯克尔：递归处理嵌套的任意深度名单

回答

相关问题