Advanced search
1 file | 236.52 KB Add to list

Understanding idiomatic traversals backwards and forwards

(2013) ACM SIGPLAN NOTICES. 48(12). p.25-36
Author
Organization
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.
Keywords
Haskell, applicative functors, traversal, idioms, FUNCTORS, traversable functors, monads, idioms, finitary containers, applicative functors

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 236.52 KB

Citation

Please use this url to cite or link to this publication:

MLA
Bird, Richard, Jeremy Gibbons, Stefan Mehner, et al. “Understanding Idiomatic Traversals Backwards and Forwards.” ACM SIGPLAN NOTICES 48.12 (2013): 25–36. Print.
APA
Bird, R., Gibbons, J., Mehner, S., Voigtländer, J., & Schrijvers, T. (2013). Understanding idiomatic traversals backwards and forwards. ACM SIGPLAN NOTICES, 48(12), 25–36. Presented at the ACM SIGPLAN Haskell Symposium co-located with ICFP.
Chicago author-date
Bird, Richard, Jeremy Gibbons, Stefan Mehner, Janis Voigtländer, and Tom Schrijvers. 2013. “Understanding Idiomatic Traversals Backwards and Forwards.” Acm Sigplan Notices 48 (12): 25–36.
Chicago author-date (all authors)
Bird, Richard, Jeremy Gibbons, Stefan Mehner, Janis Voigtländer, and Tom Schrijvers. 2013. “Understanding Idiomatic Traversals Backwards and Forwards.” Acm Sigplan Notices 48 (12): 25–36.
Vancouver
1.
Bird R, Gibbons J, Mehner S, Voigtländer J, Schrijvers T. Understanding idiomatic traversals backwards and forwards. ACM SIGPLAN NOTICES. 2013;48(12):25–36.
IEEE
[1]
R. Bird, J. Gibbons, S. Mehner, J. Voigtländer, and T. Schrijvers, “Understanding idiomatic traversals backwards and forwards,” ACM SIGPLAN NOTICES, vol. 48, no. 12, pp. 25–36, 2013.
@article{4132247,
  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.}},
  author       = {{Bird, Richard and Gibbons, Jeremy and Mehner, Stefan and Voigtländer, Janis and Schrijvers, Tom}},
  issn         = {{0362-1340}},
  journal      = {{ACM SIGPLAN NOTICES}},
  keywords     = {{Haskell,applicative functors,traversal,idioms,FUNCTORS,traversable functors,monads,idioms,finitary containers,applicative functors}},
  language     = {{eng}},
  location     = {{Boston, MA, USA}},
  number       = {{12}},
  pages        = {{25--36}},
  title        = {{Understanding idiomatic traversals backwards and forwards}},
  url          = {{http://dx.doi.org/10.1145/2503778.2503781}},
  volume       = {{48}},
  year         = {{2013}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: