R. Hinze, N. Wu, und J. Gibbons. Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, Seite 209--220. New York, NY, USA, ACM, (2013)
DOI: 10.1145/2500365.2500578
Zusammenfassung
Folds over inductive datatypes are well understood and widely used. In their plain form, they are quite restricted; but many disparate generalisations have been proposed that enjoy similar calculational benefits. There have also been attempts to unify the various generalisations: two prominent such unifications are the 'recursion schemes from comonads' of Uustalu, Vene and Pardo, and our own 'adjoint folds'. Until now, these two unified schemes have appeared incompatible. We show that this appearance is illusory: in fact, adjoint folds subsume recursion schemes from comonads. The proof of this claim involves standard constructions in category theory that are nevertheless not well known in functional programming: Eilenberg-Moore categories and bialgebras.
%0 Conference Paper
%1 citeulike:13131401
%A Hinze, Ralf
%A Wu, Nicolas
%A Gibbons, Jeremy
%B Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming
%C New York, NY, USA
%D 2013
%I ACM
%K functional-programming haskell
%P 209--220
%R 10.1145/2500365.2500578
%T Unifying Structured Recursion Schemes
%U http://dx.doi.org/10.1145/2500365.2500578
%X Folds over inductive datatypes are well understood and widely used. In their plain form, they are quite restricted; but many disparate generalisations have been proposed that enjoy similar calculational benefits. There have also been attempts to unify the various generalisations: two prominent such unifications are the 'recursion schemes from comonads' of Uustalu, Vene and Pardo, and our own 'adjoint folds'. Until now, these two unified schemes have appeared incompatible. We show that this appearance is illusory: in fact, adjoint folds subsume recursion schemes from comonads. The proof of this claim involves standard constructions in category theory that are nevertheless not well known in functional programming: Eilenberg-Moore categories and bialgebras.
%@ 978-1-4503-2326-0
@inproceedings{citeulike:13131401,
abstract = {{Folds over inductive datatypes are well understood and widely used. In their plain form, they are quite restricted; but many disparate generalisations have been proposed that enjoy similar calculational benefits. There have also been attempts to unify the various generalisations: two prominent such unifications are the 'recursion schemes from comonads' of Uustalu, Vene and Pardo, and our own 'adjoint folds'. Until now, these two unified schemes have appeared incompatible. We show that this appearance is illusory: in fact, adjoint folds subsume recursion schemes from comonads. The proof of this claim involves standard constructions in category theory that are nevertheless not well known in functional programming: Eilenberg-Moore categories and bialgebras.}},
added-at = {2019-06-18T20:47:03.000+0200},
address = {New York, NY, USA},
author = {Hinze, Ralf and Wu, Nicolas and Gibbons, Jeremy},
biburl = {https://www.bibsonomy.org/bibtex/2e1b2511a7b3edd93fe7a586b5566349d/alexv},
booktitle = {Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming},
citeulike-article-id = {13131401},
citeulike-attachment-1 = {hinze_13_unifying_1084616.pdf; /pdf/user/alexv/article/13131401/1084616/hinze_13_unifying_1084616.pdf; 908375249ce1e94b3cacb8b5b71e4d1a05d9f08e},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=2500578},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/2500365.2500578},
doi = {10.1145/2500365.2500578},
file = {hinze_13_unifying_1084616.pdf},
interhash = {bb638f196a1f074a01b918d95f2db06b},
intrahash = {e1b2511a7b3edd93fe7a586b5566349d},
isbn = {978-1-4503-2326-0},
keywords = {functional-programming haskell},
location = {Boston, Massachusetts, USA},
pages = {209--220},
posted-at = {2016-09-23 22:33:48},
priority = {3},
publisher = {ACM},
series = {ICFP '13},
timestamp = {2019-08-24T00:10:58.000+0200},
title = {{Unifying Structured Recursion Schemes}},
url = {http://dx.doi.org/10.1145/2500365.2500578},
year = 2013
}