将一个表“增长”的命令式算法转换为纯函数

Question

我用Python 3编写的程序有许多地方，它以一个（非常大的）类似于表的数字数据结构开始，并在某些算法。 （这个算法在每个地方都不一样）。

我试图将它转化为纯粹的函数式方法，因为我遇到了命令式方法的问题（难以重用，难以记忆临时步骤，很难实现“懒惰”计算，由于依赖状态而容易出错等）。

Table该类实现为词典的词典：外部词典包含行，索引为row_id;内部包含一行内的值，由column_title索引。该表的方法很简单：

# return the value at the specified row_id, column_title 
get_value(self, row_id, column_title) 

# return the inner dictionary representing row given by row_id 
get_row(self, row_id) 

# add a column new_column_title, defined by func 
# func signature must be: take a row and return a value 
add_column(self, new_column_title, func) 

到现在为止，我只是简单地添加列到原始表，以及每个函数把整个表作为参数。随着我转向纯函数，我必须使所有参数不变。所以，初始表变得不可变。任何额外的列将被创建为独立列，并只传递给那些需要它们的函数。一个典型的函数将采用初始表和几个已经创建的列，并返回一个新列。

我遇到的问题是如何实现独立列（Column）？

我可以让他们每一个字典，但它似乎非常昂贵。事实上，如果我需要对每个逻辑行中的10个字段执行操作，则需要执行10次字典查找。最重要的是，每列将包含键和值，使其大小加倍。

我可以使Column成为一个简单的列表，并在其中存储对从row_id到数组索引的映射的引用。好处是这个映射可以在对应于同一个初始表的所有列之间共享，并且一次只查找一次，它适用于所有列。但是这是否会产生其他问题？

如果我这样做，我可以走得更远，并实际存储在初始表本身的映射？我可以将Column对象的引用放回到创建它们的初始表中吗？它与我想象的功能性方法的工作方式似乎有很大的不同，但我不能看出它会造成什么问题，因为一切都是不变的。

通常情况下，函数方法对保持参数的返回值中的某个参数感到皱眉吗？它似乎不会破坏任何东西（如优化或懒惰评估），因为无论如何这个论点都是已知的。但也许我错过了一些东西。

Answer 1

这里是我会怎么做：

1. 从frozenset派生您的表类。
2. 每一行都应该是一个元组的子类。

现在你不能修改表 - >不变性，太好了！下一步 可以考虑每一个功能，您适用于 表中的突变，产生一个新问题：

f T -> T' 

如在桌子T上应用函数f这应该被理解为生产 新表T'。您也可以尝试将表格数据的实际处理对象化，并将其视为您应用或添加到 表中的操作。

add(T, A) -> T' 

这里的伟大的事情是加可减，而不是给你 一个简单的方法来模拟撤消。当你进入这个思维模式时，你的代码 变得非常容易推理，因为你没有任何可以让 搞砸的状态。

下面是如何在Python中以纯功能方式实现和处理表 结构的示例。 Imho，Python不是 是学习FP的最好的语言，因为它使得它很容易到 程序。 Haskell，F＃或Erlang是我认为更好的选择。

class Table(frozenset): 
    def __new__(cls, names, rows): 
     return frozenset.__new__(cls, rows) 

    def __init__(self, names, rows): 
     frozenset.__init__(self, rows) 
     self.names = names 

def add_column(rows, func): 
    return [row + (func(row, idx),) for (idx, row) in enumerate(rows)] 

def table_process(t, (name, func)): 
    return Table(
     t.names + (name,), 
     add_column(t, lambda row, idx: func(row)) 
     ) 

def table_filter(t, (name, func)): 
    names = t.names 
    idx = names.index(name) 
    return Table(
     names, 
     [row for row in t if func(row[idx])] 
     ) 

def table_rank(t, name): 
    names = t.names 
    idx = names.index(name) 
    rows = sorted(t, key = lambda row: row[idx]) 
    return Table(
     names + ('rank',), 
     add_column(rows, lambda row, idx: idx) 
     ) 

def table_print(t): 
    format_row = lambda r: ' '.join('%15s' % c for c in r) 
    print format_row(t.names) 
    print '\n'.join(format_row(row) for row in t) 

if __name__ == '__main__': 
    from random import randint 
    cols = ('c1', 'c2', 'c3') 
    T = Table(
     cols, 
     [tuple(randint(0, 9) for x in cols) for x in range(10)] 
     ) 
    table_print(T) 

    # Columns to add to the table, this is a perfect fit for a 
    # reduce. I'd honestly use a boring for loop instead, but reduce 
    # is a perfect example for how in FP data and code "becomes one." 
    # In fact, this whole program could have been written as just one 
    # big reduce. 
    actions = [ 
     ('max', max), 
     ('min', min), 
     ('sum', sum), 
     ('avg', lambda r: sum(r)/float(len(r))) 
     ] 
    T = reduce(table_process, actions, T) 
    table_print(T) 

    # Ranking is different because it requires an ordering, which a 
    # table does not have. 
    T2 = table_rank(T, 'sum') 
    table_print(T2) 

    # Simple where filter: select * from T2 where c2 < 5. 
    T3 = table_filter(T2, ('c2', lambda c: c < 5)) 
    table_print(T3)