순기능 데이터 구조

Purely functional data structure

컴퓨터 과학에서 순기능 데이터 구조는 순기능 언어로 구현될 수 있는 데이터 구조다.임의의 데이터 구조와 순전히 기능적인 데이터 구조 사이의 주요 차이점은 후자는 (강력하게) 불변한다는 것이다.이 제한사항은 (전체) 지속성, 빠른 객체 복사 및 스레드 안전성 등 데이터 구조가 불변 객체의 장점을 갖도록 보장한다.효율적인 순기능 데이터 구조에는 게으른 평가와 메모화가 필요할 수 있다.

정의

영구적 데이터 구조는 이전 버전의 자체를 수정하지 않고 유지하는 특성이 있다.반면에 어레이와 같은 구조는 되돌릴 수 없는 파괴적인 업데이트,[1] 즉 업데이트를 인정한다.프로그램이 어레이의 일부 인덱스에 값을 기록하면 이전 값을 더 이상 검색할 수 없다.[citation needed]

형식적으로 순수 기능적 데이터 구조는 하스켈과 같은 순수 기능적 언어로 구현될 수 있는 데이터 구조다.실제로, 그것은 데이터 구조가 튜플, 합계 유형, 제품 유형과 같은 지속적 데이터 구조와 정수, 문자, 문자열과 같은 기본 유형만을 사용하여 구축되어야 한다는 것을 의미한다.그러한 데이터 구조는 반드시 지속적이다.그러나 모든 지속적 데이터 구조가 순전히 기능적인 것은 아니다.[1]: 16 예를 들어, 영구 어레이는 지속적이고 어레이를 사용하여 구현되는 데이터 구조로, 따라서 순수하게 기능하지 않는다.[citation needed]

오카사키 교수는 '순전히 기능적인 데이터 구조'라는 책에서 파괴적인 업데이트를 마스터 셰프의 칼과 비교한다.[1]: 2 파괴적 업데이트는 취소할 수 없으므로 이전 값이 더 이상 필요하지 않은 한 사용하지 마십시오.그러나 파괴적 업데이트는 다른 기법을 사용하여 얻을 수 없는 효율성도 허용할 수 있다.예를 들어 어레이를 사용하는 데이터 구조와 파괴적 업데이트를 사용하는 데이터 구조는 어레이가 지도, 랜덤 액세스 목록 또는 순전히 기능적인 구현을 허용하는 균형 잡힌 트리로 대체되는 유사한 데이터 구조로 대체될 수 있다.그러나 접속 비용은 일정한 시간에서 로그 시간으로 증가할 수 있다.[citation needed]

데이터 구조가 순전히 작동하는지 확인

데이터 구조는 본질적으로 기능하지 않는다.예를 들어 스택은 단일 연결 목록으로 구현될 수 있다.이 구현은 스택의 유일한 운영이 이전 스택을 변경하지 않고 새로운 스택을 반환하는 한 순전히 기능적이다.그러나 언어가 순전히 기능적이지 않다면 런타임 시스템은 불변성을 보장하지 못할 수도 있다.이것은 오카사키에 의해 설명되어 있는데,[1]: 9–11 여기서 그는 두 개의 단독 링크된 리스트의 결합은 여전히 명령적인 설정을 사용하여 이루어질 수 있다는 것을 보여준다.[citation needed]

데이터 구조가 불순기능 언어로 순수하게 기능적으로 사용되도록 하기 위해 모듈이나 클래스를 사용하여 인가된 기능만을 통한 조작을 보장할 수 있다.[citation needed]

순수 기능적 데이터 구조 사용

기존 코드를 순전히 기능적인 데이터 구조를 사용하도록 적응시키는 데 있어 중심적인 난제 중 하나는 변이 가능한 데이터 구조가 이를 사용하는 기능에 대해 "숨겨진 출력"을 제공한다는 사실에 있다.순전히 기능적인 데이터 구조를 사용하기 위해 이러한 기능을 다시 쓰려면 이러한 데이터 구조를 명시적 출력으로 추가해야 한다.

예를 들어, 변경 가능한 목록을 수락하고 목록에 요소를 삽입한 다음 새 목록의 길이를 반환하는 함수를 고려해 보십시오.순기능 설정에서 목록에 새 요소를 삽입하면 새 목록이 생성되지만 원래 요소는 업데이트되지 않는다.따라서 유용하기 위해서는 순전히 기능적인 버전의 이 기능은 목록의 길이와 새로운 목록 자체를 모두 반환해야 할 가능성이 높다.가장 일반적인 경우, 이러한 방식으로 변환된 프로그램은 모든 기능 호출에서 추가 결과로 프로그램의 "상태" 또는 "저장소"를 반환해야 한다.이런 프로그램은 가게 패싱 형식으로 쓰여진다고 한다.

예

다음은 순전히 기능적으로 구현된 추상 데이터 구조의 목록이다.

설계 및 구현

컴퓨터 과학자 Chris Okasaki는 그의 저서 Pured Functional Data Structures에서 순기능 데이터 구조를 설계하고 구현하는 데 사용되는 기법을 기술하고 있는데, 그 중 작은 부분집합은 아래에 요약되어 있다.

게으름과 메모화

평가 순서가 함수의 결과를 결코 바꾸지 않기 때문에 게으른 평가는 순전히 기능적인 언어로[1]: 31 특히 흥미롭다.따라서 게으른 평가는 당연히 순기능 데이터 구조 구축에 중요한 부분이 된다.그것은 그 결과가 실제로 필요할 때만 계산을 할 수 있게 한다.따라서, 순기능 데이터 구조의 코드는 효율성의 손실 없이 효과적으로 사용될 데이터와 무시될 데이터를 유사하게 고려할 수 있다.필요한 유일한 계산은 첫 번째 종류의 데이터를 위한 것이다; 그것이 실제로 수행될 것이다.[citation needed]

효율적이고 순전히 기능적인 데이터 구조를 구축하는 데 있어 중요한 도구 중 하나는 메모화다.[1]: 31 연산이 완료되면 저장되므로 두 번 다시 수행하지 않아도 된다.이는 게으른 구현에서 특히 중요하다. 추가 평가에는 동일한 결과가 필요할 수 있지만 어떤 평가에 먼저 필요한지 알 수 없다.[citation needed]

상각분석 및 스케줄링

일부 데이터 구조는, 동적 어레이와 같이 순수하게 기능하지 않는 구조일지라도, 대부분의 시간 동안 효율적인 작업(예: 동적 어레이의 일정한 시간)을 허용하며, 거의 비효율적인 작업(예: 동적 어레이의 선형 시간)을 허용한다.그런 다음 상각은 영업의 평균 가동 시간이 효율적이라는 것을 입증하는 데 사용될 수 있다.[1]: 39 즉, 몇 가지 비효율적인 운영은 충분히 드물며, 일련의 운영이 고려되었을 때 시간 복잡성의 점증적 진화를 바꾸지 않는다.[citation needed]

일반적으로, 비효율적인 운영은 영구적인 데이터 구조에서는 허용되지 않는다. 왜냐하면 바로 이 운영은 여러 번 호출될 수 있기 때문이다.사용자가 작업에 걸리는 시간을 예측 가능하게 요구할 수 있는 실시간 시스템이나 긴급 시스템에는 허용되지 않는다.게다가, 이러한 예측 불가능성은 병렬의 사용을 복잡하게 만든다.[1]: 83 [citation needed]

이러한 문제를 피하기 위해 일부 데이터 구조는 비효율적인 운영을 연기할 수 있도록 허용한다. 이를 스케줄링이라고 한다.[1]: 84 유일한 요건은 비효율적인 운영의 연산이 그 결과가 실제로 필요하기 전에 끝나야 한다는 것이다.비효율적인 운영의 일정한 부분은 효율적 운영을 위한 다음의 호출과 동시에 수행되므로, 비효율적인 운영은 그것이 필요할 때 이미 완전히 이루어지고, 각각의 개별 운영은 효율적 상태를 유지한다.[clarification needed]

예: 대기열

상각 대기열은[1]: 65 [1]: 73 전면과 후면 두 개의 단일 연계 목록으로 구성된다.요소가 후면 목록에 추가되고 전면 목록에서 제거된다.나아가 앞줄은 비어 있을 때마다 뒷줄은 거꾸로 되어 앞줄은 되고 뒷줄은 비어 있다.각 연산의 상각된 시간 복잡성은 일정하다.목록의 각 셀은 최대 한 번에 추가, 반전 및 제거된다.후방 리스트가 뒤바뀌는 비효율적인 작업을 피하기 위해 실시간 대기열은 후방 리스트가 앞쪽 리스트만큼만 길다는 제한을 추가한다.후면 목록이 전면 목록보다 길어질 수 있도록 전면 목록을 후면 목록에 추가한 후 반전한다.이 작업은 비효율적이기 때문에 즉시 수행되지 않는다.그 대신 후속 작전에 대해 널리 퍼져 있다.따라서, 각 셀은 필요하기 전에 계산되고, 새로운 전면 목록은 새로운 비효율적인 운영을 호출할 필요가 있기 전에 완전히 계산된다.[citation needed]

참고 항목

참조

  1. ^ a b c d e f g h i j k Chris Okasaki, Cambridge University Press, 1998, ISBN0-521-66350-4

외부 링크