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

Question

在 Haskell 中，据说任何 ADT 都可以表示为乘积之和。我试图找到一种与 Tree 同构的平面类型。 , 在 Data.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所以我可以编写一个与其同构的类型而没有嵌套类型？

这个问题不是 my previous question 的重复问题.最后一个是关于用 Scott Encoding 表示嵌套类型，正​​确答案是“忽略嵌套”。这个继续询问如何展平嵌套类型(因为它是斯科特编码的特定用途所需要的，但通常不是强制性的)。

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)

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