获取嵌套列表的头部和尾部

Question

我有一个这样声明的嵌套列表类型：

data NestedList a 
= Int a
| List [NestedList a]
deriving (Show, Eq)

我正在尝试获取 NestedList 的头部和尾部，但不确定如何实现。我的尝试并没有真正成功，因为它将获得 NestedList 中的第一个 Int。我的代码是：

headList :: NestedList a -> NestedList a
headList (Int x) = Int x
headList (List x) = head $ map headList x

我明白为什么这不起作用，因为它遍历所有列表并从每个列表中获取 Int。例如：

test = List [List [Int 5]] -> headList test = Int 5, instead of List [Int 5]

我想 tail 的解决方案应该是相似的（除了列表而不是元素部分），所以任何人都可以帮助我至少让 headList 工作吗？

Answer 1

as 的 NestedList 是 a 的原子，由 Int 标记（让我们使用 A 代替）或嵌套列表as（让我们使用 N）：

data NestedList a = A a | N [NestedList a]
       deriving (Show, Eq)

那么，什么是空列表？ -- 是N[ ]。它没有头也没有尾。

什么是单例列表？ -- 如果它是 A x 或 N[A x]，它的头部就是 x.

什么是单例列表的尾部？ -- 这是一个空列表。

什么是较长列表的尾部 N(h:t)？ -- 如果 h 为 A _，则为 N t.

其他嵌套结构较多的情况涉及更多。在这种情况下，您是否希望 head 到 return 最左边的原子，并且 tail 构造一个没有最左边元素的类似嵌套结构？这可以递归地完成：

headNested (A x) = x
headNested (N xs) = headNested (head xs)

对吧？没那么简单，正如 user Bergi 在评论中指出的那样：嵌套空列表情况如何，N[ N[ ], N[ ]]？是不是也算空？（可能是）。因此，这将必须更多地参与。也许您想决定某种规范结构，并实施一个 normalize 例程，首先使用。

或者更好的是，保持结构不变，而不是遵循，切换到 returning Maybe 对头和尾，并使用那递归。

Obtain head and tail of nested list