Haskell - Dây kéo

Zippers trong Haskell về cơ bản là các con trỏ trỏ đến một số vị trí cụ thể của cấu trúc dữ liệu, chẳng hạn như tree.

Hãy để chúng tôi xem xét một tree có 5 yếu tố [45,7,55,120,56]có thể được biểu diễn dưới dạng một cây nhị phân hoàn hảo. Nếu tôi muốn cập nhật phần tử cuối cùng của danh sách này, thì tôi cần xem qua tất cả các phần tử để tiếp cận phần tử cuối cùng trước khi cập nhật nó. Đúng?

Nhưng, điều gì sẽ xảy ra nếu chúng ta có thể xây dựng cây của mình theo cách mà một cái cây có N các phần tử là một tập hợp của [(N-1),N]. Sau đó, chúng ta không cần phải vượt qua tất cả những điều không mong muốn(N-1)các yếu tố. Chúng tôi có thể cập nhật trực tiếp phần tử thứ N. Đây chính xác là khái niệm Zipper. Nó tập trung hoặc trỏ đến một vị trí cụ thể của một cây mà chúng ta có thể cập nhật giá trị đó mà không cần đi ngang qua toàn bộ cây.

Trong ví dụ sau, chúng tôi đã triển khai khái niệm Zipper trong một danh sách. Theo cách tương tự, người ta có thể triển khai Zipper trongtree hoặc một file cấu trúc dữ liệu.

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
type Zipper_List a = ([a],[a])    

go_Forward :: Zipper_List a -> Zipper_List a   
go_Forward (x:xs, bs) = (xs, x:bs)   
   
go_Back :: Zipper_List a -> Zipper_List a   
go_Back (xs, b:bs) = (b:xs, bs)    

main = do 
   let list_Ex = [1,2,3,4] 
   print(go_Forward (list_Ex,[]))       
   print(go_Back([4],[3,2,1]))

Khi bạn biên dịch và thực thi chương trình trên, nó sẽ tạo ra kết quả sau:

([2,3,4],[1]) 
([3,4],[2,1])

Ở đây chúng tôi đang tập trung vào một phần tử của toàn bộ chuỗi trong khi tiến lên hoặc trong khi lùi lại.