테이블을 순수 함수로 "확장하는"명령형 알고리즘 변환

Question

파이썬 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에서 배열 색인으로의 매핑에 대한 참조를 저장할 수 있습니다. 이 맵핑은 동일한 초기 테이블에 해당하는 모든 C 럼간에 공유 될 수 있고 한 번 조회되면 모든 C 럼에서 작동한다는 이점이 있습니다. 그러나 이것으로 다른 문제가 발생합니까?

이렇게하면 초기 테이블 자체에 실제로 매핑을 저장할 수 있습니까? Column 개체의 참조를 만든 초기 테이블로 되돌릴 수 있습니까? 기능적 접근 방식을 상상했던 것과는 아주 다른 것처럼 보입니다. 그러나 모든 것이 불변하기 때문에 어떤 문제가 발생하는지 알 수 없습니다.

일반적으로 반환 값의 참조를 인수 중 하나에 유지하는 기능적 접근 방법은 싫은가요? 논쟁이 이미 어쨌든 알려 졌기 때문에 (최적화 나 게으른 평가와 같은) 어떤 것도 망가뜨릴 것 같지 않습니다. 하지만 어쩌면 내가 뭔가를 놓친 것 같아. 여기

Answer 1

내가 어떻게 할 것입니다 :

1. 는 frozenset에서 테이블 클래스를 파생.
2. 각 행은 튜플의 서브 클래스 여야합니다.

이제 테이블을 변경할 수 없습니다.

테이블 T의 함수 f를 적용 할 때 읽어야

f T -> T' 

이 새로운 생산 : 다음 단계 는이 새로운 생산하기 위해 각 기능에게 당신이 테이블에 적용되는 돌연변이를 고려 될 수있다 테이블 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)