Преобразование императивного алгоритма, который "увеличивает" таблицу в чистые функции

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'

Это следует читать как применить функцию f к таблице T, чтобы создать новую таблицу T'. Вы также можете попытаться объективизировать фактическую обработку данных таблицы и рассматривать ее как действие, которое вы применяете или добавляете в таблицу.

add(T, A) -> T'

Самое замечательное в том, что сложение может быть вычтено, что дает вам простой способ моделирования отмены. Когда вы попадаете в такое мышление, ваш код становится очень легко рассуждать, потому что у вас нет состояния, которое могло бы испортить ситуацию.

Ниже приведен пример того, как можно реализовать и обработать структуру таблицы в Python чисто функциональным способом. Имхо, Python не лучший язык для изучения FP, потому что он позволяет легко программировать. Хаскелл, 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)