Haskell - Zippers 概念

Zippers 基本上是指向数据结构（例如树）的某个特定位置的指针。

让我们考虑一个具有 5 个元素 [45,7,55,120,56] 的树，它可以表示为完美二叉树。 如果我想更新此列表的最后一个元素，那么我需要遍历所有元素以到达最后一个元素，然后再更新它。 对吗?

但是，如果我们能够以这样的方式构建树，即具有 N 个元素的树是 [(N-1),N] 的集合，会怎么样? 。 那么，我们就不需要遍历所有不需要的 (N-1) 元素。 我们可以直接更新第N个元素。 这正是Zipper的概念。 它聚焦或指向树的特定位置，我们可以在其中更新该值，而无需遍历整个树。

在下面的示例中，我们在列表中实现了Zipper的概念。 以同样的方式，可以在树或文件数据结构中实现Zipper。

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

当你编译并执行上面的程序时，它将产生以下输出 −

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

在这里，我们在前进或后退时关注整个字符串的一个元素。