如何在没有嵌套列表的情况下编写与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以便我可以编写一个与它同构的类型而没有嵌套类型？

这个问题与我之前的问题不重复.最后一个是关于使用Scott编码表示嵌套类型,正​​确的答案是"忽略嵌套".这个人继续询问如何扁平嵌套类型(因为特定使用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)

但是,我不确定这是一般程序的实例程度.