지퍼(데이터 구조)

지퍼는 구조를 임의로 가로지르는 프로그램 작성에 편리하도록 집계 데이터 구조를 나타내는 기법으로, 특히 순기능 프로그래밍 언어에서 그 내용을 업데이트한다.지퍼는 제라드 휴에트가 1997년에 설명한 것이다.^[1]그것은 때때로 어레이와 함께 사용되는 갭 버퍼 기술을 포함시키고 일반화한다.

지퍼 기법은 목록, 나무, 기타 재귀적으로 정의된 데이터 구조에 적응할 수 있다는 점에서 일반적이다.이와 같이 변형된 데이터 구조는 개념적으로 나무나 목록이라는 것을 강조하기 위해 보통 "지퍼가 달린 트리" 또는 "지퍼가 달린 리스트"라고 부르는데 반해 지퍼는 구현의 디테일이다.

지퍼가 달린 나무에 대한 일반인의 설명은 부모에게 갈 수 있는 수술이 있는 일반적인 컴퓨터 파일 시스템일 것이다(흔히 그렇다).cd ..(), 그리고 아래로 내려갈 수 있는 가능성(cd subdirectory지퍼는 현재 경로로 가는 포인터다.뒤에서 지퍼는 데이터 구조를 변경할 때 효율적이다(기능적) 데이터 구조를 변경할 때 새롭고 약간 변경된 데이터 구조를 편집 작업에서 반환한다(현재 데이터 구조를 변경하는 대신).

예제: 양방향 목록 통과

컴퓨터 과학에서 많은 공통적인 데이터 구조는 소수의 원시적인 생성자 작업이나 관찰자 작업에 의해 생성된 구조로 표현될 수 있다.여기에는 두 가지 연산에 의해 생성될 수 있는 유한목록의 구조가 포함된다.

Empty빈 목록을 작성한다.
Cons(x, L)값을 미리 입력하거나 연결하여 목록을 작성한다.x명단의 앞쪽에L.

다음과 같은 목록[1, 2, 3]그러므로 선언이다.Cons(1, Cons(2, Cons(3, Empty)))리스트의 위치를 리스트의 전면에서 대상 위치까지의 단계 수와 같이 설명할 수 있다.좀 더 공식적으로, 리스트에 있는 위치는Cons특정 위치에서 전체 목록을 재구성하는 데 필요한 작업예를 들면,Cons(1, Cons(2, Cons( X, Cons(4, Empty)))) a Cons(2, L)그리고 aCons(1, L)X 위치에 상대적인 리스트를 재구성하기 위해 조작이 필요할 것이다. X 위치의 다른 명칭은 다음과 같다.Cons( X, Cons(4, Empty)). 위치와 함께 이 녹화를 목록 또는 목록 지퍼의 압축된 표현이라고 한다.

분명히 말씀드리면 리스트에 있는 위치는 단순히 숫자만 있는 것이 아니다.Cons운영, 그리고 그것들에 대한 다른 모든 정보들Cons; 이 경우 다시 연결해야 하는 값.여기서 이러한 값은 대상 위치에서 적용 순서대로 별도의 리스트에 편리하게 표시할 수 있다.특히, 리스트의 "3"의 맥락에서 보면[1, 2, 3, 4], 레코딩('경로'라고 부름)을 다음과 같이 나타낼 수 있다.[2, 1]어디에Cons(2, L)다음에 적용됨(Cons 1, L)원래 리스트를 다시 작성하다[3, 4].

목록 지퍼는 항상 전체 데이터 구조를 나타낸다.그러나 이 정보는 데이터 구조 내의 특정 위치의 관점에서 볼 수 있다.따라서 목록 지퍼는 컨텍스트 또는 시작점으로서의 위치와 해당 시작 위치에서 재구성을 허용하는 기록 또는 경로 둘 다로 구성된 쌍이다.특히 의 리스트-지퍼.[1, 2, 3, 4]"3"의 위치에서는 다음과 같이 나타낼 수 있다.([2, 1], [3, 4]). 이제 "3"을 "10"으로 변경하면 목록 지퍼가([2, 1], [10, 4]). 목록을 효율적으로 재구성할 수 있다.[1, 2, 10, 4]또는 이동된 다른 위치.

목록을 이렇게 나타내면 임의의 위치에 있는 Lists 및 Trees와 같은 불변의 데이터 구조에 대해 비교적 효율적인 작업을 정의할 수 있다.특히 지퍼변형을 트리에 적용하면 트리의 특정 위치에 쉽게 값을 삽입하거나 제거할 수 있다.

컨텍스트 및 차별화

지퍼의 컨텍스트 타입은 탈분류화를 통해 미적분학의 파생상품과 밀접한 관련이 있는 오리지널 타입의 변형을 통해 구성할 수 있다.The recursive types that zippers are formed from can be viewed as the least fixed point of a unary type constructor of kind $*\rightarrow *$ . For example, with a higher-order type constructor ${\text{lfp}}:(*\rightarrow *)\rightarrow *$ that constructs the least fixed point of그것의 인수는 라벨이 없는 이진 트리는 ${\text{lfp}}(T\mapsto T^{2}+1)$ ( ${\text{lfp}}(T\mapsto T^{2}+1)$ T ${\text{lfp}}(T\mapsto T^{2}+1)$ + ${\text{lfp}}(T\mapsto T^{2}+1)$ ) ${\displaystyle {\text{lfp}}(T\mapsto T^{2}+1$ )로 나타낼 수 있으며 ${\text{lfp}}(T\mapsto T^{2}+1)$ , 라벨이 없는 목록은 ${\text{lfp}}(T\mapsto T+1)$ ${\text{lfp}}(T\mapsto T+1)$ ${\text{lfp}}(T\mapsto T+1)$ + $){\text{lfp}(T\mapstoT+1$ ) 형식을 취할 수 있다 ${\text{lfp}}(T\mapsto T+1)$ 여기서, 지수화, 곱하기, 덧셈의 표기법은 각각 함수유형, 제품유형, 합계유형에 해당하는 반면, 자연수는 유한유형에 라벨을 붙인다. 이러한 방식으로 유형 생성자는 $\mathbb {N} \rightarrow \mathbb {N}$ → N ${\$ 의 다항함수와 유사하다 $\mathbb {N} \rightarrow \mathbb {N}$ ^[2]

The derivative of a type constructor can therefore be formed through this syntactic analogy: for the example of an unlabeled ternary tree, the derivative of its type constructor $(T\mapsto T^{3}+1)'$ would be equivalent to $T\mapsto 3\times T^{2}$ , analogously to the 미분학에서 총량과 전력 규칙의 사용.원래의 타입 ${\text{lfp}}(f)$ ( $){\displaystyle {\text{lfp}}}$ 위에 있는 지퍼의 컨텍스트의 타입은 원래의 타입인 $f'({\text{lfp}}(f))$ ′ ( $f'({\text{lfp}}(f))$ $f'{\text{lfp}}$ 에 적용된 타입 생성자의 파생형과 동일하다 ${\text{lfp}}(f)$ $f'({\text{lfp}}(f))$ ^[3]

그림에서 유형 1의 sentinel 노드 또는 유형 $A$ 의 값을 포함하는 노드가 있는 이진 트리의 재귀 데이터 구조를 고려하십시오.

{\text{BTree}:={\text{lfp}}(T\mapsto A\times T^{2}+1)

유형 생성자의 부분적 파생상품은 다음과 같이 계산될 수 있다.

[\displaystyle(T\mapsto A\timesto T^{2}+1)]=T\mapsto 2회 A회 T}

따라서 지퍼의 컨텍스트 타입은

{\displaystyle(T\mapsto 2\time A\time T)({\text{BTree}})=2\time A\time {\text{BTree}}

이와 같이, 우리는 라벨이 붙은 바이너리 트리의 각 비-센티넬 하위 노드의 컨텍스트는 다음과 같은 3가지로 구성되어 있음을 발견한다.

현재 노드가 상위 노드의 왼쪽 또는 오른쪽 자식인지 여부를 나타내는 유형 2의 부울 값
$현재$ 노드의 부모 레이블인 유형 A의 값
현재 노드의 상위 노드의 $다른$ 분기에 포함된 하위 트리인 BTree 유형의 노드의 형제.

In general, a zipper for a tree of type ${\text{lfp}}(f)$ consists of two parts: a list of contexts of type $f'({\text{lfp}}(f))$ of the current node and each of its ancestors up until the root node, and the value of type ${\text{lfp}}(f)$ ${\text{lfp}}(f)$ 현재 노드에 포함되어 있는지 확인하십시오.

사용하다

지퍼의 의미론은 이동의 개념을 반영하지만 기능적인 비파괴적인 방식으로 반영하기 때문에, 어떤 데이터 집합에서 포커스 또는 이동의 개념이 있는 곳에 종종 사용된다.

지퍼는 에 사용되어 왔다.

Xmonad(Xmonad), 창 포커스 및 배치 관리
Huet의 논문은 지퍼에 기초한 구조 편집자와^[4] 정리 전문가에 관한 내용을 다루고 있다.
파일 시스템(지퍼)FS) "...트랜잭션 의미론, 파일 및 디렉토리 작업 실행 취소, 스냅샷, 정적으로 가장 강력하고 반복 가능한 읽기, 클라이언트 격리 모드, 파일 및 디렉토리에 대한 포괄적 복사-온-쓰기, 내장된 통과 기능, 그리고 주기적 디렉토리 참조에 적합한 동작"을 제공하는 Haskell에서 작성되었다.^[5]
Clojure는 지퍼에 대한 폭넓은 지지를 가지고 있다.^[6]

대체 및 확장

직접수정

비기능적 프로그래밍 언어에서는 단순히 원래의 데이터 구조를 가로지르고 직접 수정하는 것이 더 편리할 수 있다(아마도 심층 복제 후, 참조를 포함할 수 있는 다른 코드에 영향을 미치지 않도록 하기 위해).

제네릭 지퍼

일반 지퍼는^[7]^[8]^[9] 각 노드를 방문하면서 연속적으로 트래버설의 상태를 포착해 기존 지퍼와 동일한 목표를 달성하는 기법이다.(참조에서 제공된 Haskell 코드는 일반 프로그래밍을 사용하여 모든 데이터 구조에 대한 통과 함수를 생성하지만, 이는 선택 사항이며, 모든 적절한 통과 함수를 사용할 수 있다.)

그러나 일반적인 지퍼는 제어의 역전을 수반하기 때문에, 그 사용의 일부는 다음에 무엇을 해야 할지를 추적하기 위해 상태 기계(또는 동등한 것)를 필요로 한다.

참조

^ 휴엣 1997
^ Joyal, André (October 1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics. 42 (1): 1–82. doi:10.1016/0001-8708(81)90052-9.
^ McBride, Conor(2001) "일반 유형의 파생상품은 원홀 컨텍스트 유형"
^ Hinze, Ralf; Jeuring, Johan (2001). "Functional Pearl: Weaving a web". Journal of Functional Programming. 11 (6): 681–689. doi:10.1017/S0956796801004129. ISSN 0956-7968. S2CID 35791452.
^ 제네릭 지퍼: 트래버설의 컨텍스트
^ jafingerhut (22 October 2010). "clojure.zip/zipper". ClojureDocs. Retrieved 15 June 2013.
^ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 1". Retrieved 29 August 2011.
^ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 2". Retrieved 29 August 2011.
^ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 3". Retrieved 29 August 2011.

추가 읽기

Huet, Gerard (September 1997). "Functional Pearl: The Zipper" (PDF). Journal of Functional Programming. 7 (5): 549–554. doi:10.1017/s0956796897002864.
Hinze, Ralf; Jeuring, Johan; Löh, Andres (May 2004). "Type-indexed data types". Science of Computer Programming. 51 (1–2): 117–151. doi:10.1016/j.scico.2003.07.001.

외부 링크

[1] 휴엣 1997

[2] Joyal, André (October 1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics. 42 (1): 1–82. doi:10.1016/0001-8708(81)90052-9.

[3] McBride, Conor(2001) "일반 유형의 파생상품은 원홀 컨텍스트 유형"

[4] Hinze, Ralf; Jeuring, Johan (2001). "Functional Pearl: Weaving a web". Journal of Functional Programming. 11 (6): 681–689. doi:10.1017/S0956796801004129. ISSN 0956-7968. S2CID 35791452.

[5] 제네릭 지퍼: 트래버설의 컨텍스트

[6] rhut (22 October 2010). "clojure.zip/zipper". ClojureDocs. Retrieved 15 June 2013.

[7] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 1". Retrieved 29 August 2011.

[8] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 2". Retrieved 29 August 2011.

[9] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 3". Retrieved 29 August 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search