哈斯克爾：遞歸處理嵌套的任意深度名單

我學習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

哈斯克爾：遞歸處理嵌套的任意深度名單

回答

相關問題