功能层次结构的组成

Question

有没有一种规范的方式来表达一个函数,它是一个有根函数树的组合？

这是一个具体的例子,我的意思是"功能树的组成".取一个根节点的树,其节点由函数标记,如下所示:

节点处的每个函数都是其子节点处的函数的组合.与树相关联的函数本身就是组合

F = a0(b0(c0(e0, e1, e2)), b1(d0(f0), d1(g0, g1)))

更明确地,F是由叶子上的函数计算的6个参数的函数:

F(x0, ... , x5) == a0(b0(c0(e0(x0), e1(x1), e2(x2))),
                      b1(d0(f0(x3)), d1(g0(x4), g1(x5))))

一般问题

给定一个有根树T,以及一个L与节点对应的函数列表T,是否有一种规范的方法来编写F参数的函数T并L返回L根据树结构化的函数的组合T？

以这种方式,组合物的"布线" - 树T- 与其内部"组件" - 列表分开L."规范"解决方案尤其应该包括自然适应该问题的表示T和L自然适应.

我怀疑这个问题在函数式编程语言中有一个简单的解决方案,但理想情况下我希望有一个像Python这样的动态类型命令式语言的解决方案,类似于

def treecomp(tree, list_of_funcs):
    ...
    return function

F = treecomp(T, L)

附录

与此同时,我想出了自己的解决方案(发布在下面).

虽然我对其经济和概念简单性感到满意,但我仍然对其他本质上不同的方法感兴趣,特别是那些利用Python中缺乏或支持不足的另一种语言的优势的方法.

使用适当的数据结构 - 基本上不会重现所需的输出! - 功能编程习惯应该能够实现非常短的解决方案.

Answer 1

这将是面向对象编程（OOP）的一个很好的候选者。例如，您可以使用这三个类

对于处理树结构，递归方法通常更容易。

或者，您也可以通过在元组中嵌入元组来直接构建递归结构。例如

n1 = ( 'L', 'e0' )
n2 = ( 'L', 'e1' )
n3 = ( 'L', 'e2' )
n4 = ( 'N', 'c0', n1, n2, n3 )
n5 = ( 'N', 'b0', n4 )

这不是完整的树，但可以轻松扩展。只需使用即可print (n5)查看结果。

这不是唯一的方法，可能会有变化。对于每个元组，第一项是一个字母，指定它是叶“L”还是节点“N”——这将使递归函数更容易。第二项是名称（取自您的绘图）。对于一个节点，其他项都是子节点。

（注意，我曾经使用“元组中的元组”来实现霍夫曼编码算法——它也适用于树结构）。