haskell - 在 Haskell 中创建任意嵌套的列表结构

Question

鉴于以下问题：

对于一个爱好项目，我遇到了一个有趣的问题，就是将树的平面表示转换为嵌套数据结构。一棵树的平面表示如下所示：

0 0 1 1 2 3 2 1

每个数字表示树中的嵌套级别。转换为嵌套结构后，它应该如下所示（方括号是 Python 的列表语法）：

[ 0, 0, [ 1, 1, [ 2, [ 3 ], 2], 1]]

我怎样才能在 Haskell 中做到这一点？

score 14 · Accepted Answer

在 Haskell 中，列表的所有元素都需要具有相同的类型。所以你不能有一个列表，其中一个元素是整数，另一个元素是列表。因此[1, [2, 3]]会导致 Haskell 中的类型错误。

因此，如果您想表示这样的任意嵌套结构，您需要为此定义自己的类型。这可能看起来像这样：

data Tree a =
    Leaf a
  | Branch [Tree a]

该类型的值可能如下所示：

Branch [
  Leaf 0, Leaf 0,
  Branch [
    Leaf 1, Leaf 1, Branch [
      Leaf 2, Branch [
        Leaf 3],
      Leaf 2],
    Leaf 1]]

1 回答 1