Vết sẹo hữu ích cho việc gì?

Question

Trong bài báo có tiêu đề "The Zipper" của Huet, ông cũng đề cập đến những vết sẹo như là một biến thể của khóa kéo. So với dây kéo, mà đã trở nên khá nổi tiếng trong cộng đồng Haskell, những vết sẹo là khá nhiều chưa từng nghe thấy. Có rất ít thông tin về chúng trong chính bài báo và bất cứ nơi nào trên internet từ những gì tôi có thể tìm thấy.

Vì vậy, tôi phải hỏi, có phải họ không hữu ích chút nào hoặc có điều gì đó hữu ích cho họ, nhưng hầu hết mọi người chỉ không biết về họ?

Answer 1

Nó chỉ là một điều chỉnh nhỏ cho loại cây để làm cho một số hoạt động hiệu quả hơn.

Trọng tâm giấy (ha ha) trên hoa hồng - cây có nút có số lượng con tùy ý. Mã từ giấy là trong OCaml nhưng nó rất đơn giản để dịch để Haskell:

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

Để tóm tắt ngắn gọn, ý tưởng của dây kéo là đại diện cho một vị trí trong một cấu trúc dữ liệu bằng cách ngữ cảnh của nó. Ngữ cảnh của một nút trong cây hoa hồng bao gồm đường dẫn bạn đã đi xuống cây để tới được nút cha mẹ và đường dẫn bạn đã đi dọc theo danh sách anh chị em để đến được chính nút đó.

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

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

này cho phép bạn phóng to trên một vị trí trong một cây mà không quên nơi bạn đã đến bằng cách đi bộ right và down, và sau đó xây dựng lại cây bằng cách rút lui left và thu nhỏ 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 

Hãy xem định nghĩa của up. Phải mất t, l và r - nút hiện đang được tập trung và anh chị em của nó - và kết hợp chúng lại với nhau thành một danh sách trẻ em. Nó quên nút bạn đang xem. Theo đó, down tập trung bạn vào con ngoài cùng bên trái của trọng tâm hiện tại. Nếu bạn cần phải đi up và sau đó quay trở lại nút được tập trung trước đó, bạn phải đi bộ right dọc theo danh sách trở lại vị trí của bạn, đó là hoạt động của O (n).

Ý tưởng của Huet về việc để lại 'vết sẹo' trên cây là giúp việc trở lại một đứa trẻ tập trung trước đây thuận tiện hơn. Ông trang bị cho các nhà xây dựng Rose với một trọng tâm của riêng mình, thay thế danh sách các trẻ em với một danh sách dây kéo.

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

Các Path và Pos loại vẫn không thay đổi:

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

Bây giờ, khi bạn đi up và sau đó trở lại down, bạn đừng quên những gì trước đây bạn đã nhìn vào.

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)