지퍼

지침

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

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

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

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

Zipper의 동작

Zipper는 Node 트리를 탐색하는 함수형 방식을 제공해요.

모든 Zipper 호출은 새로운 Zipper 객체를 반환해야 해요. Zipper가 값을 바꾸지 않는다면(즉, Set* 메서드를 호출하지 않았다면), Zipper는 같은 기반 트리를 사용해야 해요. Set* 메서드를 호출하면 새로운 Zipper는 새로운 트리를 갖고, 원래 트리는 바뀌지 않은 채로 남아요.

포커스를 유효하지 않은 Node로 옮기는 Zipper 호출은 오류를 반환해야 해요.