python - 功能层次结构的组成

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，以及与 T 的节点对应的函数列表 L，是否存在一个规范的 编写参数 T 和 L 的函数 F 的方法，返回 L< 中函数的组合 根据树结构 T?

通过这种方式，组合的“接线”——树 T——与其内部“组件”——列表 L 分开了。 “规范”解决方案尤其应该包括自然适应此问题的 T 和 L 的表示。

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

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

F = treecomp(T, L)

附录

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

虽然我对它的经济性和概念简单性感到满意，但我仍然会对其他本质上不同的方法感兴趣，尤其是那些利用另一种语言的优势而 Python 缺乏或支持不佳的方法。

预感

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

Answer 1

是的，所以这对我来说听起来很有趣。所以我试了一下，结果如下。

class Node(object):
    def __init__(self, parents, fn):
        self.parents = parents
        self.fn = fn

    def get_number_of_args(self):
        if not self.parents:
            return 1
        if not hasattr(self, '_cached_no_args'):
            self._cached_no_args = sum(
                parent.get_number_of_args() for parent in self.parents
            )
        return self._cached_no_args

    def compose(self):
        if not self.parents:
            def composition(*args):
                return self.fn(*args)
            return composition

        fns = []
        fns_args = []
        for parent in self.parents:
            fns.append(parent.compose())
            fns_args.append(parent.get_number_of_args())
        number_of_args = sum(fns_args)
        length = len(self.parents)

        def composition(*args):
            if len(args) != number_of_args:
                raise TypeError
            sub_args = []
            last_no_args = 0
            reached_no_args = 0
            for i in range(length):
                fn = fns[i]
                no_args = fns_args[i]
                reached_no_args += no_args
                args_cut = args[last_no_args: reached_no_args]
                sub_call = fn(*args_cut)
                sub_args.append(sub_call)
                last_no_args = no_args
            return self.fn(*sub_args)

        return composition

您没有指定实现树结构的方式，所以我将节点和功能组合到一个结构中(您始终可以自己进行映射)。现在的用法:

>>> def fn(x):
...     return x
>>> def fn2(x):
...    return 1
>>> def add(x, y):
...    return x + y
>>> n1 = Node([], fn)
>>> n2 = Node([], fn2)
>>> n3 = Node([n1, n2], add)
>>> fn = n3.compose()
>>> print(fn(5, 7))
6

如预期。随意测试它(实际上我还没有在更深的树上尝试过)，如果您发现任何问题，请告诉我。