Eu estava lendo um capítulo em LYAH que realmente não fazia sentido para mim. Entendo que os zíperes podem atravessar arbitrariamente uma estrutura semelhante a uma árvore, mas preciso de alguns esclarecimentos. Além disso, os zíperes podem ser generalizados para qualquer estrutura de dados?
ds.data-structures
functional-programming
tree
n_ary_crazy
fonte
fonte
Respostas:
Um zíper, em geral, é uma estrutura de dados com um buraco. Os zíperes são usados para percorrer / manipular estruturas de dados, e o furo corresponde ao foco atual do percurso. Normalmente, também há um elemento da estrutura de dados em consideração, para que se tenha um zíper (lista) e uma lista ou um zíper (árvore) e uma árvore. O zíper permite que o programador se mova com eficiência pela estrutura de dados, substituindo até o elemento em foco. O par do zíper e o elemento no foco atendem à restrição de que colocar o elemento no foco no furo fornece a estrutura de dados original.
Os zíperes podem ser generalizados para tipos de dados indutivos arbitrários. O conceito pode ser definido de maneira indexada por tipo (consulte Tipos de dados indexados por tipo ). Eles também estão relacionados à idéia da derivada de uma estrutura de dados e foram estudados a partir de uma perspectiva teórica de categoria .
fonte
Em geral, um zíper é um par de coisas: é uma estrutura com um buraco, um foco , representando onde você está na estrutura, juntamente com um caminho , registrando como chegou a esse foco. (Esse caminho é a trilha de migalhas de pão de LYAH.)
O caminho é como você realmente aplica alterações à estrutura: "desça, vá para a esquerda, aumente o valor". Ao aplicar repetidamente "ir para cima" (
go_upno artigo de Huet ) neste ponto, você pode refazer suas etapas e terminar com uma cópia nova e mutada da estrutura original.Eles podem de fato ser generalizados para outras estruturas:
fonte