Backtracking iterators Export

@inproceedings{citeulike:5921707, abstract = {Iterating over the elements of an abstract collection is usually done in ML using a fold-like higher-order function provided by the data structure. This article discusses a different paradigm of iteration based on purely functional, immutable cursors. Contrary to fold-like iterators, the iteration can be cleanly interrupted at any step. Contrary to imperative cursors (such as those found in C++ and Java libraries) it is possible to backtrack the iterator to a previous step. Several ways to iterate over binary trees are examined and close links with G\&\#233;rard Huet's Zipper are established. Incidentally, we show the well-known two-lists implementation of functional queues arising from a Zipper -based breadth-first traversal.}, address = {New York, NY, USA}, author = {Filli\^{a}tre, Jean C.}, booktitle = {ML '06: Proceedings of the 2006 workshop on ML}, citeulike-article-id = {5921707}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1159876.1159885}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1159876.1159885}, doi = {10.1145/1159876.1159885}, isbn = {1-59593-483-9}, keywords = {backtrack, fold, induction, iterators, structural-induction}, location = {Portland, Oregon, USA}, pages = {55--62}, posted-at = {2009-10-11 18:51:07}, priority = {2}, publisher = {ACM}, title = {Backtracking iterators}, url = {http://dx.doi.org/10.1145/1159876.1159885}, year = {2006} }

TY - CONF ID - citeulike:5921707 L3 - citeulike-article-id:5921707 N2 - Iterating over the elements of an abstract collection is usually done in ML using a fold-like higher-order function provided by the data structure. This article discusses a different paradigm of iteration based on purely functional, immutable cursors. Contrary to fold-like iterators, the iteration can be cleanly interrupted at any step. Contrary to imperative cursors (such as those found in C++ and Java libraries) it is possible to backtrack the iterator to a previous step. Several ways to iterate over binary trees are examined and close links with Gérard Huet's Zipper are established. Incidentally, we show the well-known two-lists implementation of functional queues arising from a Zipper -based breadth-first traversal. CY - Portland, Oregon, USA SN - 1-59593-483-9 AD - New York, NY, USA EP - 62 TI - Backtracking iterators PB - ACM T2 - ML '06: Proceedings of the 2006 workshop on ML SP - 55 KW - backtrack KW - fold KW - induction KW - iterators KW - structural-induction AU - Filliâtre, Jean PY - 2006/// UR - http://dx.doi.org/10.1145/1159876.1159885 ER -