Picture of wind turbine against blue sky

Open Access research with a real impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs.

The Energy Systems Research Unit (ESRU) within Strathclyde's Department of Mechanical and Aerospace Engineering is producing Open Access research that can help society deploy and optimise renewable energy systems, such as wind turbine technology.

Explore wind turbine research in Strathprints

Explore all of Strathclyde's Open Access research content

Clowns to the left of me, jokers to the right (pearl) : dissecting data structures

Mcbride, Conor (2008) Clowns to the left of me, jokers to the right (pearl) : dissecting data structures. In: POPL '08 Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, New York, NY, pp. 287-295. ISBN 978-1-59593-689-9

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

This paper introduces a small but useful generalisation to the 'derivative' operation on datatypes underlying Huet's notion of 'zipper', giving a concrete representation to one-hole contexts in data which is undergoing 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 here as a generic program, albeit for polynomial functors only. The notion is certainly applicable more widely, but here I prefer to concentrate 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. Further, the derivative is readily recovered from the dissection. Indeed, it is the dissection structure which delivers Huet's operations for navigating zippers. The original motivation for dissection was to define 'division', capturing the notion of leftmost hole, canonically distinguishing values with no elements from those with at least one. Division gives rise to an isomorphism corresponding to the remainder theorem in algebra. By way of a larger 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 online and compiles with recent extensions to the Glasgow Haskell Compiler.