什么是 Zipper 数据结构，我应该使用它吗? [英] What is the Zipper data structure and should I be using it?

问题描述

问题很简单:我无法理解 Zipper 数据结构.>

我的问题与它与树的使用有关.

我想了解如何使用 zipper 更改树节点.以及如何不复制整棵树(或其中的大部分).

请澄清我是否对拉链有误.也许它无法帮助更新树?
或者，也许可以更新树而我只是看不到路?

解决方案

让我们从列表的 Zipper 模拟开始.如果您想修改列表的第 n 个元素，则需要 O(n)，因为您必须复制第 n-1 个元素.相反，您可以将列表保留为结构((前 n-1 个元素颠倒)第 n 个元素(剩余元素)).例如，可在 3 处修改的列表 (1 2 3 4 5 6) 将表示为 ((2 1) 3 (4 5 6)).现在，您可以轻松地将 3 更改为其他内容.您还可以轻松地将焦点向左移动 ((1) 2 (3 4 5 6)) 和向右移动 ((3 2 1) 4 (5 6)).

拉链与应用于树木的想法相同.您代表树中的某个焦点加上上下文(上至父级，下至子级)，它以一种形式为您提供整个树，在焦点处可以轻松修改，并且可以轻松上下移动焦点.

The question is simple: I cannot understand the Zipper data structure.

My question is related to its uses with a Tree.

I want to understand how can I change the tree node using zipper. And how not to copy the whole tree (or the most part of it).

Please, clarify if I'm wrong with zipper. Maybe it cannot help with the tree update?
Or, maybe, it is possible to update the tree and I just cannot see the way?

解决方案

Let's start with the Zipper-analog for lists. If you'd like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).

A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it's easily modifiable at the focus and it's easy to move the focus up and down.

这篇关于什么是 Zipper 数据结构，我应该使用它吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！