如何在Haskell中实现嵌套列表的深度反转操作

Haskell 原生的同构列表[a]无法直接表示深度不同的嵌套结构，且固定长度的异质元组也不支持通用的递归遍历，所以我们需要先自定义递归的嵌套列表类型，再实现深度反转逻辑。

1. 定义嵌套列表代数数据类型 #

-- Elem代表单个元素节点，List代表嵌套列表节点
data NestedList a = Elem a | List [NestedList a] deriving (Show, Eq)

2. 实现深度反转函数 #

逻辑非常直接：

• 单个元素节点不需要修改，直接返回
• 列表节点需要先递归反转每一个子元素，再反转当前层级的元素顺序，就能得到内外全反转的效果

-- 你也可以把内置的reverse替换为你自己实现的rev函数，逻辑完全一致
deepRev :: NestedList a -> NestedList a
deepRev (Elem x) = Elem x
deepRev (List xs) = List (reverse (map deepRev xs))

3. 测试你的示例场景 #

你给出的输入结构(A,B,(C,(D,E)),F)对应的嵌套列表构造方式如下：

input :: NestedList Char
input = List [Elem 'A', Elem 'B', List [Elem 'C', List [Elem 'D', Elem 'E']], Elem 'F']

调用deepRev input得到的输出为：

List [Elem 'F',List [List [Elem 'E',Elem 'D'],Elem 'C'],Elem 'B',Elem 'A']

完全匹配你需要的(F,((E,D),C),B,A)的结果。

内容的提问来源于stack exchange，提问作者Ellis Thompson