Title: Understanding idiomatic traversals backwards and forwards
Authors: Bird, Richard * ×
Gibbons, Jeremy *
Mehner, Stefan *
Schrijvers, Tom *
Voigtlaender, Janis * #
Issue Date: 2013
Publisher: ACM Press
Series Title: ACM SIGPLAN Notices vol:48 issue:12 pages:25-36
Conference: Haskell Symposium location:Boston, USA date:23-24 September 2013
Abstract: We present new ways of reasoning about a particular class of effectful Haskell
programs, namely those expressed as idiomatic traversals. Starting out with a
specific problem about labelling and unlabelling binary trees, we extract a general inversion law,
applicable to any monad, relating a traversal over the elements
of an arbitrary traversable type to a traversal that goes in the opposite
direction. This law can be invoked to show that, in a suitable sense, unlabelling
is the inverse of labelling. The inversion law, as well as a number of
other properties of idiomatic traversals, is a corollary of a more general theorem
characterising traversable functors as finitary containers:
an arbitrary traversable object can be decomposed uniquely into
shape and contents, and traversal be understood in terms of those.
Proof of the theorem involves the properties of traversal in a
special idiom related to the free applicative functor.
ISSN: 0362-1340
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
uitbaf.pdfarticle Accepted 230KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science