函数层次结构的组成

Is there a canonical way to express a function that is a composition of a rooted tree of functions?

是否有一种规范的方法来表示一个由根函数树组成的函数?

Here is a concrete example of what I mean by "composition of a tree of functions." Take a rooted tree whose nodes are labelled by functions, like so:

这里有一个具体的例子来说明我所说的“函数树的组合”。取一个节点被函数标记的根树，如下所示:

Each function at a node is a composition of the functions at its child nodes. The function that is associated to the tree, itself, is the composition

节点上的每个函数都是子节点上函数的组合。与树本身相关联的函数是合成

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

More explicitly, F is a function of 6 arguments that are evaluated by the functions at the leaves:

更明确地说，F是一个由6个参数组成的函数，由叶子处的函数求值:

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

General question

一般性的问题

• Given a rooted tree T, and a list L of functions corresponding to the nodes of T, is there a canonical way to write a function F of the arguments T and L that returns the composition of the functions in L structured according to the tree T?
• 给定一个根树T和一个对应于T节点的函数L，是否有一种规范的方法来写出一个函数F(参数T和L)返回L中根据树T构造的函数的组合?

In this way, the "wiring" of the composition—the tree T—is separated from its internal "components"—the list L. A "canonical" solution should include, in particular, representations of T and L that are naturally adapted to this problem.

通过这种方式，组合的“布线”——树T——与它的内部“组件”(列表L)分离，“规范”的解决方案应该包括，特别是，T和L的表示，它们自然地适应了这个问题。

I suspect that this problem has a trivial solution in a functional programming language, but ideally I would like to have a solution in a dynamically-typed imperative language like Python, something like

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

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

F = treecomp(T, L)

Addendum

In the meantime, I came up with my own solution (posted below).

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

While I am satisfied with its economy and conceptual simplicity, I would nevertheless be interested in other essentially different approaches, especially those that leverage strengths in another language that are either lacking or poorly supported in Python.

尽管我对它的经济性和概念的简洁性感到满意，但我仍然对其他本质上不同的方法感兴趣，特别是那些利用另一种语言的优势的方法，这些方法在Python中要么缺乏，要么缺乏支持。

Hunch

With proper data structures—that don't essentially reproduce the desired output!—functional-programming idioms should enable a very short solution.

有了正确的数据结构，就不会产生想要的输出!函数式编程的习惯用法应该能够提供一个非常简短的解决方案。

5 个解决方案

#1

Right, so this sounds like an interesting thing to me. So I've gave it a try and here's the result.

对，这听起来很有趣。我试过了，结果是这样的。

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

You didn't specify the way you implement the tree structure so I combined both nodes and functions into one structure (you can always do mapping yourself). Now the usage:

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

>>> 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

as expected. Feel free to test it (I actually haven't tried it on deeper tree) and let me know if you find any issues.

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

#2

We define a function treecomp that returns the composition of a list of functions L structured according to a rooted tree T, by taking L and T as separate arguments:

我们定义了一个函数treecomp，它通过将L和T作为独立的参数，返回由根树T构成的函数列表的组成。

F = treecomp(T, L)

Unlike the other solutions proposed thus far, it isn't complicated by unnecessary bookkeeping, such as tracking the number of leaves or arguments (which is better handled by decorators, besides).

与迄今为止提出的其他解决方案不同，它不需要进行不必要的簿记，比如跟踪叶节点的数量或参数(除此之外，decorator处理得更好)。

A simple construction of treecomp

A straightforward realization of treecomp is the following: it merely generates a symbolic (string) expression of the tree composition. Evaluation on arguments is then just a matter of plugging them in and evaluating the resulting expression.

treecomp的一个直接实现如下:它仅仅生成树组合的一个符号(字符串)表达式。对参数的求值就是把它们代入并求出结果表达式。

This naive idea can be implemented using fairly basic data structures: lists for the tree and functions, and a simple class for the function-labeled tree. (Namedtuples would also do. However, by using a class with special comparison methods, we can write more semantically natural code.)

这个幼稚的想法可以使用相当基本的数据结构来实现:树和函数的列表，以及函数标记的树的简单类。(Namedtuples也会做。但是，通过使用具有特殊比较方法的类，我们可以编写更符合语义的自然代码。

Data structures

The most economical encoding of a rooted tree as a flat list is as a list of "node addresses." In a comment to @JeD, I hinted that this could be done by "drawing" the tree:

将根树编码为平面列表最经济的方法是将其编码为“节点地址”列表。在@JeD的评论中，我暗示这可以通过“绘制”树来实现:

T = [(0,),
         (0, 0),
             (0, 0, 0),
                 (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2),
         (0, 1),
             (0, 1, 0),
                 (0, 1, 0, 0),
             (0, 1, 1),
                 (0, 1, 1, 0), (0, 1, 1, 1)]

Here (0,) is the node corresponding to a0, (0, 0) is the node corresponding to b0, (0, 1) is the node corresponding to b1, and so forth, like the numbering of sections in a book. The longest (or "highest") tuples are the leaves.

这里(0)是a0对应的节点，(0,0)是b0对应的节点，(0,1)是b1对应的节点，以此类推，就像书中章节的编号一样。最长的(或“最高”)元组是叶。

The list of functions L can then be given as a list matching the order of nodes in T:

函数L的列表可以作为匹配T中节点的顺序的列表:

L = [a0, b0, c0, e0, e1, e2, b1, d0, f0, d1, g0, g1]

Since the nodes of the tree T are labeled by the functions in L, it will be convenient to have a data structure for that. We define a class that records a node's address and the literal name of the function labeling it; its methods implement comparisons relative to the partial ordering of the tree (where the root is the minimum element):

由于树T的节点是由L中的函数标记的，因此使用数据结构来表示它是很方便的。我们定义一个类来记录节点的地址和标记它的函数的文字名称;其方法实现了相对于树的部分排序(根是最小元素)的比较:

class SymbNode:
    '''Class that records a node's address and symbol.'''

    def __init__(self, addr, symb):
        self.addr = addr
        self.symb = symb

    def __len__(self): # how "high" a node is above the root
        return len(self.addr)

    def _compare(self, other, segment):
        return self.addr == other.addr[:segment]

    def __le__(self, other):
        return self._compare(other, segment=len(self))

    def begets(self, other):
        return self._compare(other, segment=-1)

Implementation

The simple two-step mechanism of treecomp is implemented below. By normalizing the order of the list of SymbNodes, we can build up a symbolic expression by simply "peeling off" each layer of the tree as we move up it.

treecomp的简单两步机制实现如下。通过规范化符号节点列表的顺序，我们可以通过在树向上移动时“剥离”树的每一层来构建一个符号表达式。

from functools import partial
from operator import attrgetter

def treecomp(tree, funcs):
    '''Returns the composition of a tree of functions.'''
    symbtree = makesymbtree(tree, funcs)
    symbexp = makesymbexp(symbtree)
    return partial(evalsymbexp, symbexp=symbexp)

FUNC_CALL = '{func}({{}})'

def makesymbtree(tree, funcs):
    '''Returns the symbolic expression of a tree composition.'''
    symbols = [FUNC_CALL.format(func=func.__name__) for func in funcs]
    symbtree = sorted((SymbNode(*x) for x in zip(tree, symbols)),
                      key=attrgetter('addr'))
    symbtree.sort(key=len)
    return symbtree

def makesymbexp(symbtree):
    root = symbtree[0]
    if len(symbtree) == 1: # symbtree is a leaf node
        return root.symb
    symbargs = [makesymbexp(subsymbtree(symbtree, root=node))
                for node in symbtree if root.begets(node)]
    return root.symb.format(','.join(symbargs))

def subsymbtree(symbtree, root):
    subsymbtree = [node for node in symbtree if root <= node]
    return subsymbtree

ARGS = 'args[{idx}]'

def evalsymbexp(symbexp, *args):
    '''Returns the evaluation of a symbolic expression on arguments.'''
    argnames = [ARGS.format(idx=str(n)) for n, _ in enumerate(args)]
    return eval(symbexp.format(*argnames))

Verification

Because of the compartmentalization of treecomp, we only need to verify that the function makesymbexp generates the correct symbolic expression, and that the function evalsymbexp properly evaluates symbolic expressions.

由于treecomp的划分，我们只需要验证函数makesymbexp是否生成正确的符号表达式，以及函数evalsymbexp是否正确地计算符号表达式。

The (essentially one-line) function evalsymbexp is supposed to take a string template and plug in the argument names 'args[0]', 'args[1]', etc., then evaluate the result. It evidently does that.

evalsymbexp(本质上是一行)函数应该取一个字符串模板，并插入参数名“args[0]”、“args[1]”等，然后计算结果。这显然是。

As for makesymbexp, we can gain confidence in its correctness, in lieu of a formal proof (which we eschew), by checking its output on some test data. Take, for example, the following functions:

对于makesymbexp，我们可以通过检查它在某些测试数据上的输出来获得对其正确性的信心，而不是通过正式的证明(我们避免使用正式的证明)。以下列职能为例:

def D(x): return 2*x
def M(x): return -x
def S(*xs): return sum(xs)

a0 = S
b0, b1 = D, S
c0, d0, d1 = S, D, S
e0, e1, e2, f0, g0, g1 = D, M, D, M, D, M

With T and L as above, we can check that we get the right symbolic expression:

通过上述T和L，我们可以检验我们是否得到了正确的符号表达式:

makesymbexp(makesymbtree(T, L))

indeed yields the string

实际上收益率的字符串

'S(D(S(D({}),M({}),D({}))),S(D(M({})),S(D({}),M({}))))'

To check the delegation of treecomp to evalsymbexp, as a partial function, I verified that the value of

为了检查将treecomp委托给evalsymbexp的部分函数，我验证了

F = treecomp(T, L)
F(x0, x1, x2, x3, x4, x5)

agreed with the value of

同意…的价值

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

on 1000 random samples of x0, … , x5 drawn from the integers between -100 and 100.

从-100到100的整数中抽取1000个x0，…，x5的随机样本。

#3

Since you want to decouple Functions and Trees you can do this:

既然你想解耦函数和树，你可以这样做:

#root=RootNode, funcs=Map from Node to function, values=list of inputs
#nodes need isLeaf and children field
def Func(root,funcs,values):
    #check if leaf
    if root.isLeaf:
        #removes value from list
        val=values.pop(0)
        #returns function of root
        #(can be identity if you just want to input values)
        return funcs[root](val)

    #else we do a recursive iteration:
    else:
        nextVals=[]
        #for each child
        for child in root.children:
            #call this function->DFS for roots, removes values that are used
            nextVals.append(Func(child,funcs,values))
        #unpack list and call function
        return funcs[root](*nextVals)

Here an example:

下面一个例子:

class Node:
    children=[]
    isLeaf=False

    def __init__(self,isLeaf):
        self.isLeaf=isLeaf

    def add(self,n):
        self.children.append(n)




def Func(root,funcs,values):
    #check if leaf
    if root.isLeaf:
        #removes value from list
        val=values.pop(0)
        #returns function of root
        #(can be identity if you just want to input values)
        return funcs[root](val)

    #else we do a recursive iteration:
    else:
        nextVals=[]
        #for each child
        for child in root.children:
            #call this function->DFS for roots, removes values that are used
            nextVals.append(Func(child,funcs,values))
        #unpack list and call function
        return funcs[root](*nextVals)


def sum3(a,b,c):
    return a+b+c


import math

funcMap={}
funcMap[root]=sum3

root=Node(False)
layer1=[Node(True) for i in range(3)]
for i in range(3):
    root.add(layer1[i])
    funcMap[layer1[i]]=math.sin




print Func(root,funcMap,[1,2,3])
print math.sin(1)+math.sin(2)+math.sin(3)

this returns the same value (Using python 2.7)

这将返回相同的值(使用python 2.7)

#4

Here's a simple example that I've cooked up:

我做了一个简单的例子:

from collections import deque

class Node(object):
    def __init__(self, children, func):
        self.children = children
        if children:
            self.leaf_count = sum(c.leaf_count for c in children)
        else:
            self.leaf_count = 1  # It is a leaf node.

        self.func = func

    def __call__(self, *args):
        if not self.children:
            assert len(args) == 1, 'leaf can only accept 1 argument.'
            return self.func(*args)  # Base case.

        d_args = deque(args)
        func_results = []
        for child in self.children:
            f_args = [d_args.popleft() for _ in xrange(child.leaf_count)]
            func_results.append(child(*f_args))
        assert not d_args, 'Called with the wrong number of arguments'
        return self.func(*func_results)

Basically, the "trick" is to keep track of how many leaf nodes each node has since the number of leaf nodes are the number of arguments that it is expected to accept.

基本上，“诀窍”是跟踪每个节点有多少叶节点，因为叶节点的数量是它希望接受的参数的数量。

• If a node is a leaf, then simply call it's delegate function with the single input argument.
• 如果一个节点是一个叶子，那么只需用一个输入参数调用它的委托函数。
• If a node is not a leaf, then call each child supplying the arguments according to the number of leaf nodes that are in the child's subtree.
• 如果节点不是叶子，则调用每个提供参数的子节点，根据子树中的叶节点数。

A few implementation notes:

一些实现说明:

I used a collections.deque to pull the correct number args of to pass to the child. This is for efficiency since deque lets us take those arguments in O(1) time. Otherwise, we'd be left with something like:

我用了一个集合。deque把正确的数字args传给孩子。这是为了提高效率，因为deque允许我们在O(1)时间内使用这些参数。否则，我们会得到如下结果:

for child in self.children:
    f_args = args[:child.leaf_count]
    args = args[child.leaf_count:]
    func_results.append(child(*args))

But that is O(N) time at each pass. For small trees it probably doesn't matter. For big trees it might matter a lot :-).

但是每次都是O(N)时间。对于小树来说，这可能并不重要。对大树来说，这可能很重要。

I also used a static member for the leaf_count which means that you need to build your tree from leaves to root. Of course you could use different strategies depending on the problem constraints. e.g. you could construct your tree and then fill in the leaf_count as a single pass after the tree is built before you start evaluating functions, or you could turn leaf_count into a function (@property) that counts the leaves on every call (which might get expensive for large trees).

我还为leaf_count使用了一个静态成员，这意味着需要从叶到根构建树。当然，您可以根据问题约束使用不同的策略。例如，您可以构建您的树，然后在构建树之后，在开始计算函数之前填写leaf_count，或者您可以将leaf_count转换为一个函数(@property)，该函数计算每次调用的叶子数量(对于大型树来说，这可能会很昂贵)。

And now some tests... The simplest case that I could think of was if the leaf nodes are all associated with the identity function and then the non-leaf nodes are a function that adds the input values. In this case, the result should always be the sum of the input values:

现在一些测试……我能想到的最简单的情况是，如果叶节点都与标识函数相关联，那么非叶节点就是一个添加输入值的函数。在这种情况下，结果应该总是输入值的和:

def my_sum(*args):
    return sum(args)

def identity(value):
    return value

e0, e1, e2, f0, g0, g1 = [Node([], identity) for _ in xrange(6)]
c0 = Node([e0, e1, e2], my_sum)
d0 = Node([f0], my_sum)
d1 = Node([g0, g1], my_sum)
b0 = Node([c0], my_sum)
b1 = Node([d0, d1], my_sum)
a0 = Node([b0, b1], my_sum)

arg_tests = [
    (1, 1, 1, 1, 1, 1),
    (1, 2, 3, 4, 5, 6)
]
for args in arg_tests:
    assert a0(*args) == sum(args)
print('Pass!')

#5

This would be a good candidate for object-oriented programming (OOP). For example, you could use these three classes

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

1. Node
2. 节点
3. Leaf
4. 叶
5. Tree
6. 树

For working with tree structures, recursive methods are usually easier.

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

Alternatively, you can also directly build recursive structure by embedding tuples within tuples. For example

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

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

This is not your complete tree, but it can be easily expanded. Just use print (n5) to see the result.

这不是完整的树，但是可以很容易地扩展。使用print (n5)来查看结果。

This is not the only way, there could be variations. For each tuple, the first item is a letter specifying if it is a leaf "L" or a node "N"--this will make it easier for recursive functions. The second item is the name (taken from your drawing). For a node, the other items are the children nodes.

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

(n.b. I once used the "tuples within tuples" to implement the Huffmann encoding algorithm--it also works with a tree structure).

(n.b.我曾经使用“元组内的元组”来实现霍夫曼编码算法——它也适用于树结构)。