지퍼

지침

이진 트리를 위한 지퍼 만들기

지퍼는 자료 구조 안을 탐색하고 조작하는 순수 함수형 방식이에요. 지퍼는 기본적으로 하나의 자료 구조와, 그 자료 구조 안을 가리키는 포인터(포커스라고 불러요)를 담고 있어요.

예를 들어 각 노드가 값과 자식 노드의 배열을 담고 있는 로즈 트리가 있다면, 지퍼는 다음과 같은 연산을 지원할 수 있어요:

• from_tree (로즈 트리에서 지퍼를 꺼내요. 포커스는 루트 노드에 있어요)
• to_tree (지퍼에서 로즈 트리를 꺼내요)
• value (포커스 노드의 값을 가져와요)
• prev (포커스를 같은 부모의 이전 자식으로 옮기고, 새로운 지퍼를 반환해요)
• next (포커스를 같은 부모의 다음 자식으로 옮기고, 새로운 지퍼를 반환해요)
• up (포커스를 부모로 옮기고, 새로운 지퍼를 반환해요)
• set_value (포커스 노드의 값을 설정하고, 새로운 지퍼를 반환해요)
• insert_before (포커스 노드 앞에 새로운 서브트리를 삽입해요. 삽입한 서브트리는 포커스 노드의 prev가 되고, 새로운 지퍼를 반환해요)
• insert_after (포커스 노드 뒤에 새로운 서브트리를 삽입해요. 삽입한 서브트리는 포커스 노드의 next가 되고, 새로운 지퍼를 반환해요)
• delete (포커스 노드와 모든 서브트리를 제거해요. 포커스는 가능하면 next 노드로, 그럴 수 없으면 가능한 경우 prev 노드로, 그것도 안 되면 부모 노드로 이동하고, 새로운 지퍼를 반환해요)