Generic Discrimination: Sorting and Paritioning Unshared Data in Linear Time Export

@inproceedings{citeulike:4313805, abstract = {We introduce the notion of discrimination as a generalization of both sorting and partitioning and show that worst-case linear-time discrimination functions (discriminators) can be defined generically , by (co-)induction on an expressive language of order denotations . The generic definition yields discriminators that generalize both distributive sorting and multiset discrimination. The generic discriminator can be coded compactly using list comprehensions, with order denotations specified using Generalized Algebraic Data Types (GADTs). A GADT-free combinator formulation of discriminators is also given.}, address = {New York, NY, USA}, author = {Henglein, Fritz}, booktitle = {ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming}, citeulike-article-id = {4313805}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1411204.1411220}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1411204.1411220}, citeulike-linkout-2 = {http://lambda-the-ultimate.org/node/3277}, citeulike-linkout-3 = {ftp://ftp.diku.dk/diku/semantics/papers/D-582.pdf}, doi = {10.1145/1411204.1411220}, isbn = {978-1-59593-919-7}, keywords = {algorithms, combinators, discrimination, equivalence, gadts, generics, haskell, sorting}, location = {Victoria, BC, Canada}, pages = {91--102}, posted-at = {2009-04-20 13:32:38}, priority = {0}, publisher = {ACM}, title = {Generic Discrimination: Sorting and Paritioning Unshared Data in Linear Time}, url = {http://dx.doi.org/10.1145/1411204.1411220}, year = {2008} }

TY - CONF ID - citeulike:4313805 L3 - citeulike-article-id:4313805 N2 - We introduce the notion of discrimination as a generalization of both sorting and partitioning and show that worst-case linear-time discrimination functions (discriminators) can be defined generically , by (co-)induction on an expressive language of order denotations . The generic definition yields discriminators that generalize both distributive sorting and multiset discrimination. The generic discriminator can be coded compactly using list comprehensions, with order denotations specified using Generalized Algebraic Data Types (GADTs). A GADT-free combinator formulation of discriminators is also given. CY - Victoria, BC, Canada SN - 978-1-59593-919-7 AD - New York, NY, USA EP - 102 TI - Generic Discrimination: Sorting and Paritioning Unshared Data in Linear Time PB - ACM T2 - ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming SP - 91 KW - algorithms KW - combinators KW - discrimination KW - equivalence KW - gadts KW - generics KW - haskell KW - sorting AU - Henglein, Fritz PY - 2008/// UR - http://dx.doi.org/10.1145/1411204.1411220 ER -