顛倒Haskell中的自定義嵌套列表

Question

我正在嘗試顛倒Haskell中的嵌套列表。據我所知，嵌套的列表不是在Haskell，所以我定義了一個一件事：

flatten :: NestedList a -> [a] 
flatten (Elem x) = [x] 
flatten (SubList x) = concatMap flatten x 

現在我想給我寫反向功能：

data NestedList a = Elem a | SubList [NestedList a] 

我也有一個扁平化的功能。該功能定義爲：

myreverse :: NestedList a -> NestedList a 

我認爲這是有道理的，因爲我只是重新排列列表中的元素。

我明白如何編寫一個基本的反向函數，而且我也知道，對於Haskell的標準列表reverse已經定義了。

我的問題是：如何處理列表頭部也是列表的情況？我所知道的需要發生的事情是，我將名單的頭部顛倒過來，放回到尾巴的背面。但如何實現這一目標？

Answer 1

爲什麼不這樣

rev :: NestedList a -> NestedList a 
rev (Elem a) = Elem a 
rev (SubList xs) = SubList $ map rev $ reverse xs 

如果添加導出（顯示），以您的數據定義，

Prelude> rev $ SubList [Elem 1, SubList [Elem 2, Elem 3]] 
SubList [SubList [Elem 3,Elem 2],Elem 1] 

Prelude> rev $ SubList [Elem 1, SubList []] 
SubList [SubList [],Elem 1] 

Answer 2

你的嵌套列表實際上是在leavess元素樹：

    SubList 
      /  \ 
     SubList   Elem 4 
    / |  \ 
Elem 1 Elem 2 Elem 3 

所以你的myreverse將是一個水平翻轉，即遞歸正如其他答案指出的那樣，每個列表的0在SubList。

這裏的教訓：可視化數據結構有助於理解和實施對它們的操作。