Clowns to the Left of me, Jokers to the right: Dissecting Data Structures Export

@article{citeulike:2291184, abstract = {This paper, submitted as a 'pearl', introduces a small but useful generalisation to the 'derivative' operation on datatypes underlying Huet's notion of 'zipper' (Huet 1997; McBride 2001; Abbott et al. 2005b), giving a concrete representation to one-hole contexts in data which is in mid-transformation. This operator, 'dissection', turns a container-like functor into a bifunctor representing a one- hole context in which elements to the left of the hole are distinguished in type from elements to its right. I present dissection for polynomial functors, although it is certainly more general, preferring to concentrate here on its diverse applications. For a start, map-like operations over the functor and fold-like operations over the recursive data structure it induces can be expressed by tail recursion alone. Moreover, the derivative is readily recovered from the dissection, along with Huet's navigation operations. A further special case of dissection, 'division', captures the notion of leftmost hole, canonically distinguishing values with no elements from those with at least one. By way of a more practical example, division and dissection are exploited to give a relatively efficient generic algorithm for abstracting all occurrences of one term from another in a first-order syntax. The source code for the paper is available online1 and compiles with recent extensions to the Glasgow Haskell Compiler.}, address = {New York, NY, USA}, author = {Mcbride, Conor}, citeulike-article-id = {2291184}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1328897.1328474}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1328897.1328474}, citeulike-linkout-2 = {http://strictlypositive.org/CJ.pdf}, doi = {10.1145/1328897.1328474}, issn = {0362-1340}, journal = {SIGPLAN Not.}, keywords = {data\_structures}, month = {January}, number = {1}, pages = {287--295}, posted-at = {2008-07-02 13:26:51}, priority = {2}, publisher = {ACM}, title = {Clowns to the Left of me, Jokers to the right: Dissecting Data Structures}, url = {http://dx.doi.org/10.1145/1328897.1328474}, volume = {43}, year = {2008} }

TY - JOUR ID - citeulike:2291184 L3 - citeulike-article-id:2291184 N2 - This paper, submitted as a ‘pearl’, introduces a small but useful generalisation to the ‘derivative’ operation on datatypes underlying Huet’s notion of ‘zipper’ (Huet 1997; McBride 2001; Abbott et al. 2005b), giving a concrete representation to one-hole contexts in data which is in mid-transformation. This operator, ‘dissection’, turns a container-like functor into a bifunctor representing a one- hole context in which elements to the left of the hole are distinguished in type from elements to its right. I present dissection for polynomial functors, although it is certainly more general, preferring to concentrate here on its diverse applications. For a start, map-like operations over the functor and fold-like operations over the recursive data structure it induces can be expressed by tail recursion alone. Moreover, the derivative is readily recovered from the dissection, along with Huet’s navigation operations. A further special case of dissection, ‘division’, captures the notion of leftmost hole, canonically distinguishing values with no elements from those with at least one. By way of a more practical example, division and dissection are exploited to give a relatively efficient generic algorithm for abstracting all occurrences of one term from another in a first-order syntax. The source code for the paper is available online1 and compiles with recent extensions to the Glasgow Haskell Compiler. IS - 1 JF - SIGPLAN Not. SN - 0362-1340 AD - New York, NY, USA EP - 295 TI - Clowns to the Left of me, Jokers to the right: Dissecting Data Structures PB - ACM VL - 43 SP - 287 KW - data_structures AU - Mcbride, Conor PY - 2008/01// UR - http://dx.doi.org/10.1145/1328897.1328474 ER -