Во-во, я тоже охренел :) Размышляю, написать об этом в докладе подробно или упомянуть вскользь и сказать "Кайфуйте самостоятельно". Пока из-за нехватки времени склоняюсь ко второму варианту :)
Это ссылка на Олега Киселёва, там, похоже, zipper'ы по-другому сделаны, на Delimited Continuations.
Цитата: Our treatment of zipper is quite different from that of Huet (JFP, 1997) and Hinze and Jeuring (JFP 2001). Our zipper is polymorphic over the data structure to traverse, and the zipper creation procedure is generic and does not depend on the data structure at all. Different data structures or different realizations of the same abstract data structure can use the same zipper and the same zipper creation and manipulation functions. Our zipper type depends only on the interface (but not the implementation!) of a traversal function. Our zipper is a derivative of a traversal function rather than that of a data structure itself.
Первая производная даёт zipper, который позволяет модифицировать элемент в дырке за O(1). Автор утверждает, что вторая производная (Second Order Zipper) даёт дополнительную функциональность, в частности, позволяет делать splice структур за O(1).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
carisma_sensei
no subject
Date: 2007-10-07 11:22 am (UTC)no subject
Date: 2007-10-07 11:57 am (UTC)no subject
Date: 2007-10-08 09:08 am (UTC)no subject
Date: 2007-10-08 09:27 am (UTC)Цитата:
Our treatment of zipper is quite different from that of Huet (JFP,
1997) and Hinze and Jeuring (JFP 2001). Our zipper is polymorphic over
the data structure to traverse, and the zipper creation procedure is
generic and does not depend on the data structure at all. Different
data structures or different realizations of the same abstract data
structure can use the same zipper and the same zipper creation and
manipulation functions. Our zipper type depends only on the interface
(but not the implementation!) of a traversal function. Our zipper is a
derivative of a traversal function rather than that of a data
structure itself.
no subject
Date: 2007-10-07 04:36 pm (UTC)Ещё в ту же копилку
Date: 2007-10-07 06:00 pm (UTC)Первая производная даёт zipper, который позволяет модифицировать элемент в дырке за O(1). Автор утверждает, что вторая производная (Second Order Zipper) даёт дополнительную функциональность, в частности, позволяет делать splice структур за O(1).
Ну и ещё
Date: 2007-10-07 06:34 pm (UTC)http://okmij.org/ftp/Computation/Continuations.html#zipper
Конкурентные зипперы на одной структуре, с любым уровнем изоляции. Правда реализация, похоже, совсем другая.
no subject
Date: 2007-10-07 08:48 pm (UTC)no subject
Date: 2007-10-07 08:51 pm (UTC)