Dây kéo hai chiều

Question

Lấy cảm hứng từ câu hỏi gần đây về lưới 2d ở Haskell, tôi tự hỏi liệu nó có thể tạo ra một dây kéo hai chiều để theo dõi vị trí trong danh sách các danh sách hay không. Một dây kéo một chiều trong danh sách cho phép chúng tôi thực sự di chuyển cục bộ trong một danh sách lớn (ví dụ phổ biến là trình chỉnh sửa văn bản). Nhưng cho phép nói rằng chúng tôi có thứ nguyên thứ hai như sau:

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]] 

Chúng tôi có thể tạo một số loại cấu trúc dữ liệu dây kéo để di chuyển không hiệu quả sang trái và phải nhưng lên xuống trong lưới ở đây? Nếu vậy, điều gì sẽ xảy ra nếu chúng ta thay thế danh sách các danh sách bằng một danh sách vô hạn các danh sách vô hạn, chúng ta có thể tiếp tục chuyển động hiệu quả không?

Answer 1

Không khá, không. Một trong những khía cạnh quan trọng của cách hoạt động của zippers là chúng đại diện cho một vị trí trong một cấu trúc bằng một đường dẫn được sử dụng để tiếp cận nó, cộng với các đoạn thừa được tạo trên đường đi, với kết quả cuối cùng mà bạn có thể quay lại dọc theo đường dẫn đó và xây dựng lại cấu trúc anh đi. Bản chất của các đường dẫn có sẵn thông qua cấu trúc dữ liệu do đó hạn chế dây kéo.

Vì các vị trí được xác định bằng đường dẫn, nên mỗi đường dẫn riêng biệt thể hiện một vị trí khác nhau, vì vậy bất kỳ cấu trúc dữ liệu nào có nhiều đường dẫn đến cùng một giá trị đều không thể sử dụng được bằng dây kéo - ví dụ, xem xét danh sách vòng hoặc bất kỳ cấu trúc khác với đường dẫn vòng lặp.

Chuyển động tùy ý trong không gian 2D không thực sự phù hợp với các yêu cầu trên, vì vậy chúng tôi có thể suy ra rằng dây kéo 2D nhất thiết sẽ bị hạn chế. Có lẽ bạn sẽ bắt đầu từ nguồn gốc, đi một con đường xuyên qua cấu trúc, và sau đó quay trở lại dọc theo con đường đó một khoảng cách để đạt được các điểm khác, ví dụ. Điều này cũng ngụ ý rằng đối với bất kỳ điểm nào trong cấu trúc, có những điểm khác mà chỉ có thể đạt được thông qua nguồn gốc.

Điều bạn có thể làm là xây dựng một số khái niệm khoảng cách 2D vào cấu trúc dữ liệu, để bạn đi theo một đường dẫn xuống qua cấu trúc, các điểm "bên dưới" bạn gần nhau; ý tưởng là để giảm thiểu số lượng backtracking cần thiết trung bình để di chuyển một khoảng cách ngắn trong không gian 2D. Điều này kết thúc bằng cách gần như cùng một cách tiếp cận cần thiết để tìm kiếm không gian 2D theo khoảng cách - tìm kiếm lân cận gần nhất, giao diện hình học hiệu quả, loại điều đó - và có thể được thực hiện với cùng một loại cấu trúc dữ liệu, cụ thể là space partitioning để tạo cây tìm kiếm chiều cao hơn. Thực hiện một dây kéo cho quadtree, một kd-tree hoặc các cấu trúc tương tự rất đơn giản, giống như bất kỳ cây nào khác.

Answer 2

Bạn có thể sử dụng một cái gì đó đơn giản như mã sau đây. Chúng tôi biểu diễn một bảng theo các hàng trên cùng của phần tử đã chọn, các hàng dưới cùng của phần tử đã chọn, cộng với các phần tử ở bên trái của phần tử đã chọn và các phần tử ở bên phải của phần tử đã chọn.

Các hàng trên cùng và phần tử bên trái được lưu trữ theo thứ tự ngược lại để cho phép chuyển động hiệu quả.

Tôi không chắc chắn nếu điều này đủ điều kiện như một dây kéo mặc dù, bởi vì mặc dù chúng tôi giữ một "vị trí" trong cấu trúc dữ liệu, nó không phải là một "con đường".

-- 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 

thậm chí này hoạt động cho các danh sách vô hạn -

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