E. de Vries, and A. Löh. Proceedings of the 10th ACM SIGPLAN workshop on Generic programming - WGP '14, page 83--94. New York, NY, USA, ACM Press, (2014)
DOI: 10.1145/2633628.2633634
Abstract
We introduce the sum-of-products (SOP) view for datatype-generic programming (in Haskell). While many of the libraries that are commonly in use today represent datatypes as arbitrary combinations of binary sums and products, SOP reflects the structure of datatypes more faithfully: each datatype is a single n-ary sum, where each component of the sum is a single n-ary product. This representation turns out to be expressible accurately in GHC with today's extensions. The resulting list-like structure of datatypes allows for the definition of powerful high-level traversal combinators, which in turn encourage the definition of generic functions in a compositional and concise style. A major plus of the SOP view is that it allows to separate function-specific metadata from the main structural representation and recombining this information later.
%0 Conference Paper
%1 deVries2014True
%A de Vries, Edsko
%A Löh, Andres
%B Proceedings of the 10th ACM SIGPLAN workshop on Generic programming - WGP '14
%C New York, NY, USA
%D 2014
%I ACM Press
%K 03b15-higher-order-logic-type-theory 68n18-functional-programming-and-lambda-calculus 68p05-data-structures haskell
%P 83--94
%R 10.1145/2633628.2633634
%T True Sums of Products
%U http://dx.doi.org/10.1145/2633628.2633634
%X We introduce the sum-of-products (SOP) view for datatype-generic programming (in Haskell). While many of the libraries that are commonly in use today represent datatypes as arbitrary combinations of binary sums and products, SOP reflects the structure of datatypes more faithfully: each datatype is a single n-ary sum, where each component of the sum is a single n-ary product. This representation turns out to be expressible accurately in GHC with today's extensions. The resulting list-like structure of datatypes allows for the definition of powerful high-level traversal combinators, which in turn encourage the definition of generic functions in a compositional and concise style. A major plus of the SOP view is that it allows to separate function-specific metadata from the main structural representation and recombining this information later.
%@ 9781450330428
@inproceedings{deVries2014True,
abstract = {{We introduce the sum-of-products (SOP) view for datatype-generic programming (in Haskell). While many of the libraries that are commonly in use today represent datatypes as arbitrary combinations of binary sums and products, SOP reflects the structure of datatypes more faithfully: each datatype is a single n-ary sum, where each component of the sum is a single n-ary product. This representation turns out to be expressible accurately in GHC with today's extensions. The resulting list-like structure of datatypes allows for the definition of powerful high-level traversal combinators, which in turn encourage the definition of generic functions in a compositional and concise style. A major plus of the SOP view is that it allows to separate function-specific metadata from the main structural representation and recombining this information later.}},
added-at = {2019-03-01T00:11:50.000+0100},
address = {New York, NY, USA},
author = {de Vries, Edsko and L\"{o}h, Andres},
biburl = {https://www.bibsonomy.org/bibtex/2b0313770928c5ab12dac1538155f733d/gdmcbain},
booktitle = {Proceedings of the 10th ACM SIGPLAN workshop on Generic programming - WGP '14},
citeulike-article-id = {14363147},
citeulike-attachment-1 = {devries_14_true.pdf; /pdf/user/gdmcbain/article/14363147/1138234/devries_14_true.pdf; f8d14dc02432406616a087d153d8c844b876b8e8},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=2633634},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/2633628.2633634},
comment = {Sydney Paper Club 2018-06-27:'https://www.meetup.com/Sydney-Paper-Club/events/pssrqpyxjbkb/'},
doi = {10.1145/2633628.2633634},
file = {devries_14_true.pdf},
interhash = {25f585fc90fa673434e0a8e21bf9ed54},
intrahash = {b0313770928c5ab12dac1538155f733d},
isbn = {9781450330428},
keywords = {03b15-higher-order-logic-type-theory 68n18-functional-programming-and-lambda-calculus 68p05-data-structures haskell},
location = {Gothenburg, Sweden},
pages = {83--94},
posted-at = {2018-06-04 00:38:57},
priority = {5},
publisher = {ACM Press},
series = {WGP '14},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{True Sums of Products}},
url = {http://dx.doi.org/10.1145/2633628.2633634},
year = 2014
}