흉터 란 무엇입니까?

Question

Huet의 "The Zipper"라는 제목의 논문에서 그는 지퍼의 변형으로 흉터를 언급합니다. 하스켈 지역 사회에서 꽤 잘 알려진 지퍼와 비교하면, 흉터는 거의 들리지 않았습니다. 종이 자체와 인터넷상의 어느 곳에서든 내가 찾을 수있는 정보는 거의 없습니다.

그래서 나는 그들이 전혀 유용하지 않거나 유용 할 수있는 것이 있습니까?하지만 대부분의 사람들은 단지 그것에 대해 모른다.

Answer 1

특정 작업을보다 효율적으로 수행하기 위해 트리 유형을 약간 조정했습니다.

논문에서는 장미 나무에 초점을 맞 춥니 다.이 나무의 노드에는 임의의 수의 자식이 있습니다. 종이에서 코드를 OCaml에 있지만 하스켈로 번역하는 것은 매우 간단합니다 : 짧게 요약하자면

data Rose a = Leaf a | Rose [Rose a] 

는 지퍼의 아이디어는 상황하여 데이터 구조의 위치을 표현하는 것입니다. 장미 트리에있는 노드의 컨텍스트는 노드의 상위 노드에 도달하기 위해 트리를 가져간 경로와 노드 자체에 도달하기 위해 형제 목록을 따라 가져온 경로로 구성됩니다.

는

data Path a = Top | Node (Path a) [Rose a] [Rose a] 

data Pos a = Pos { focus :: Rose a, path :: Path a } 

이것은 당신이 right 및 down을 도보로 어디 있었는지 잊지 않고 나무의 위치를 ​​확대하고 left 후퇴하고 up을 축소하여 트리를 재 구축 할 수 있습니다.

right, down, left, up :: Pos a -> Maybe (Pos a) 
right (Pos _ Top) = Nothing 
right (Pos _ (Node _ _ [])) = Nothing 
right (Pos t (Node p ls (r:rs))) = Just $ Pos r (Node p (t:ls) rs) 

down (Pos (Leaf _) _) = Nothing 
down (Pos (Rose []) _) = Nothing 
down (Pos (Rose (t:ts)) p) = Just $ Pos t (Node p [] ts) 

left (Pos _ Top) = Nothing 
left (Pos _ (Node _ [] _)) = Nothing 
left (Pos t (Node p (l:ls) rs) = Just $ Pos l (Node p ls (t:rs)) 

up (Pos _ Top) = Nothing 
up (Pos t (Node p l r)) = Just $ Pos (Rose (l ++ t:r)) p 

up의 정의를 살펴보십시오. t, l 및 r - 현재 포커스가있는 노드 및 그 형제 -을 단일 하위 자식 목록으로 분쇄합니다. 그것은 당신이보고있는 노드를 잊어 버린다. 따라서 down은 현재 포커스의 가장 왼쪽 하위에 초점을 맞 춥니 다. up으로 이동 한 다음 이전에 초점을 맞춘 노드로 다시 되돌아 가려면 right을 다시 걸어서 O (n) 작업을 수행해야합니다.

나무에 '흉터'를 남겨 두는 Huet의 생각은 이전에 집중된 어린이에게 돌아 오는 것이 더 편리하도록하는 것입니다. 그는 Rose 생성자에 초점을 맞추어 어린이 목록을 목록 지퍼로 대체합니다.

data SRose a = -- for "scarred rose" 
     SLeaf a 
    | SEmpty -- replaces (Rose []) 
    | SRose [SRose a] (SRose a) [SRose a] 

는 Path 및 Pos 유형은 변경되지 :

data SPath a = STop | SNode (SPath a) [SRose a] [SRose a] 
data SPos a = SPos { sfocus :: Rose a, spath :: SPath a } 

을 지금, 당신은 up 가서 다시 down, 당신은 당신이 이전에보고 된 것 잊지 마세요 때.

up' (SPos _ STop) = Nothing 
up' (SPos t (SNode p l r)) = Just $ SPos (SRose l t r) p 

down' (SPos (SLeaf _) _) = Nothing 
down' (SPos SEmpty _) = Nothing 
down' (SPos (SRose l t r) p) = Just $ SPos t (SNode p l r)