如何在没有嵌套列表的情况下编写与 Tree 同构的类型？

Question

在Haskell中，据说任何ADT都可以表示为乘积之和。我正在尝试在 Data.Tree.

上找到与 Tree 同构的平面类型

Tree a = Node a [Tree a] -- has a nested type (List!)

我想为没有嵌套类型的 Tree 写一个功能相同的定义：

Tree = ??? -- no nested types allowed

为此，我尝试编写代数类型的递归关系：

L a = 1 + a * L a
T a = a * L (T a)

内联 L，我有：

T a = a * (1 + T a * L (T a))
T a = a * (1 * T a * (1 + T a * L (T a)))
T a = a * (1 + T a * (1 + T a * (1 + T a * L (T a))))

那是行不通的，所以我停下来做了乘法，结果是：

T a = a + a * T a + a * T a * T a ...

与以下内容相同：

T a = a * (T a) ^ 0 + a * (T a) ^ 1 + a * (T a) ^ 2 ...

那是乘积之和，但是无穷大。我不能在 Haskell 中写那个。通过滥用代数：

(T a) - (T a) ^ 2 = a * T a
- (T a) ^ 2 - a * T a + (T a) = 0

求解 T a，我发现：

T a = 1 - a

这显然没有任何意义。所以，回到最初的问题：如何将 Tree 从 Data.Tree 展平，这样我就可以编写一个与它同构的类型，而无需嵌套类型？

此问题与不重复。最后一个是关于用 Scott 编码表示嵌套类型，正确答案是 "ignore the nesting"。这个继续询问无论如何如何扁平化嵌套类型（因为 Scott 编码的特定用途需要它，但通常不是强制性的）。

Answer 1

一旦你到了

T a = a * (1 + T a * L (T a))

你可以继续

    = a + a * T a * L (T a)   -- distribute
    = a + T a * (a * L (T a)) -- commute and reassociate
    = a + T a * T a           -- using your original definition of T backwards

所以你到达了

data Tree a = Leaf a | InsertLeftmostSubtree (Tree a) (Tree a)

不过，我不确定这在多大程度上是一般过程的实例。

Answer 2

在阅读任何答案之前，我认为这是一个有趣的谜题，并得出了与公认答案等同的东西：

data Tree' a = Node a [Tree' a] deriving (Show, Eq, Ord)
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Eq, Ord)

除此之外，我编写了转换函数，这似乎是唯一可能的方式：

convert :: Tree' a -> Tree a
convert (Node x [])     = (Leaf x)
convert (Node x (t:ts)) = Branch (convert t) $ convert (Node x ts)

convert' :: Tree a -> Tree' a
convert' (Leaf x)      = Node x []
convert' (Branch t ts) = Node x $ convert' t : subtrees
  where (Node x subtrees) = convert' ts

这些函数的实现并不能证明正确性，但它们的类型检查、没有非穷尽的模式匹配并且似乎适用于简单输入（即 convert . convert' == id）这一事实有助于建议数据类型彼此同构，这是令人鼓舞的。

至于如何构建这样一个东西的一般结构，我的想法与接受的答案中的类型代数不同，所以我的思考过程可能有助于推导出一般方法。最主要的是注意到 [x] 可以按照通常的方式转换为 data List a = Nil | Cons a (List a)。因此，我们需要将该转换应用于 [Tree' a] 字段，同时还保留额外的 a "above" [Tree' a]。因此，我的 Leaf a 自然而然地等同于 Nil，但有一个额外的 a；那么 Branch 构造函数类似于 Cons b (List b).

我认为您可以对包含列表的任何数据构造函数执行类似的操作：给定 Constructor a b [c]，您将其转换为新类型中的两个构造函数：

data Converted a b c = Nil a b | Cons c (Converted a b c)

如果旧构造函数中有两个列表，您可以为每个列表提供一个构造函数，用于仅向其中一个列表添加一个项目：

data Old a b c = Old a [b] [c]

data New a b c = Done a
               | AddB b (New a b c)
               | AddC c (New a b c)

如何在没有嵌套列表的情况下编写与 Tree 同构的类型？

How to write a type that is isomorphic to Tree without nested lists?

haskell

functional-programming

algebraic-data-types