2 차원 지퍼

Question

하스켈의 2 차원 격자에 관한 최근의 질문에 영감을 받아리스트 목록에서 위치를 추적하기 위해 2 차원 지퍼를 만들 수 있는지 궁금합니다. 목록에있는 1 차원 지퍼를 사용하면 큰 목록에서 로컬로 효율적으로 이동할 수 있습니다 (일반적인 예는 텍스트 편집기입니다).

grid = 
    [[ 1, 2, 3, 4, 5] 
    ,[ 6, 7, 8, 9,10] 
    ,[11,12,13,14,15] 
    ,[16,17,18,19,20] 
    ,[21,22,23,24,25]] 

우리가 효율적으로뿐만 아니라 왼쪽과 오른쪽하지만 최대 여기 그리드에서 아래로 이동 지퍼 데이터 구조의 어떤 종류를 만들 수 :하지만 우리는 이와 같은 두 번째 차원을 말할 수? 그렇다면리스트를 무한리스트로 무한리스트로 대체한다면 여전히 효율적인 운동을 할 수 있을까요?

Answer 1

아니요 상당히, 아니요. 지퍼가 작동하는 주요 측면 중 하나는 구조에서 경로에 따라 도달하는 데 사용 된 경로와 그에 따라 생성 된 추가 조각을 나타내며 그 결과에 따라 되돌아와 구조를 다시 빌드 할 수 있다는 것입니다. 너가. 따라서 데이터 구조를 통해 사용할 수있는 경로의 특성에 따라 지퍼가 구속됩니다.

위치는 경로로 식별되므로 각각의 고유 한 경로는 다른 위치를 나타내므로 동일한 값에 대한 다중 경로가있는 모든 데이터 구조는 지퍼와 함께 사용할 수 없습니다. 예를 들어 순환 목록 또는 루핑 경로가있는 다른 구조체.

2D 공간에서 임의의 이동이 위의 요구 사항에 실제로 맞지 않으므로 2D 지퍼가 반드시 제한적 일 것이라고 추론 할 수 있습니다. 어쩌면 원점에서 출발하여 구조를 통과 한 다음 그 경로를 따라 어느 정도 거리를두고 다른 지점에 도달 할 수 있습니다. 이것은 또한 구조의 모든 점에 대해 원점을 통해서만 도달 할 수있는 다른 점도 있음을 의미합니다.

당신이 수있는는 데이터 구조에 2D 거리의 일부 개념을 구축합니다. 따라서 구조를 통과하는 경로를 따라갈 때 "아래"지점이 서로 가깝습니다. 아이디어는 2D 공간에서 짧은 거리를 이동하기 위해 평균적으로 필요한 역 추적의 양을 최소화하는 것입니다. 이것은 에 가까운 거리 접근 - 가장 가까운 이웃 검색, 효율적인 기하학적 교차점, 그 종류의 2D 공간을 검색하는 데 필요한 동일한 접근 방식이되고 결국 같은 종류의 데이터 구조, 즉 space partitioning을 사용하여 만들 수 있습니다. 고차원 검색 트리. quadtree, kd-tree 또는 유사한 구조의 지퍼를 구현하는 것은 다른 트리와 마찬가지로 간단합니다.

Answer 2

그럼 다음 코드와 같은 간단한 코드를 사용할 수 있습니다. 선택한 요소의 맨 위 행, 선택된 요소의 맨 아래 행 및 선택된 요소의 왼쪽에있는 요소와 선택한 요소의 오른쪽에있는 요소로 테이블을 나타냅니다.

상단 행과 왼쪽 요소는 효율적인 이동을 위해 역순으로 저장됩니다.

데이터 구조에서 "위치"를 보유하고 있지만 "경로"가 아니기 때문에 이것이 지퍼로 간주되는지 확실하지 않습니다.

-- Table sel left right top bottom 
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show 

left :: Table a -> Table a 
left tab@(Table _ [] _ _ _) = tab 
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs 

right :: Table a -> Table a 
right tab@(Table _ _ [] _ _) = tab 
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs 

up :: Table a -> Table a 
up tab@(Table _ _ _ [] _) = tab 
up (Table sel ls rs (t:ts) bs) = Table sel' ls' rs' ts (b:bs) 
    where 
    (ls',(sel':rs')) = splitAt (length ls) t 
    b = ls ++ (sel:rs) 

down :: Table a -> Table a 
down tab@(Table _ _ _ _ []) = tab 
down (Table sel ls rs ts (b:bs)) = Table sel' ls' rs' (t:ts) bs 
    where 
    (ls',(sel':rs')) = splitAt (length ls) b 
    t = ls ++ (sel:rs) 

tableToList :: Table a -> [[a]] 
tableToList (Table sel ls rs ts bs) = (reverse ts) ++ [ls ++ (sel:rs)] ++ bs 

listToTable :: [[a]] -> Table a 
listToTable [] = error "cannot make empty table" 
listToTable ([]:_) = error "cannot make empty table" 
listToTable ((t:tr):ts) = Table t [] tr [] ts 

이도 무한리스트 작동 -

selected :: Table a -> a 
selected (Table sel _ _ _ _) = sel 

a :: Table Int 
a = listToTable $ replicate 10 [1..] 

selected a     #=> 1 
selected $ down a   #=> 1 
selected $ right $ down a #=> 2