A Smart View on Datatypes

with Exequiel Rivas. ICFP 2015.PDFCode


Left-nested list concatenations, left-nested binds on the free monad, and left-nested choices in many non-determinism monads have an algorithmically bad performance. Can we solve this problem without losing the ability to pattern-match on the computation? Surprisingly, there is a deceptively simple solution: use a smart view to pattern-match on the datatype. We introduce the notion of smart view and show how it solves the problem of slow left- nested operations. In particular, we use the technique to obtain fast and simple implementations of lists, of free monads, and of two non-determinism monads.


author    = {Mauro Jaskelioff and Exequiel Rivas},
title     = {Functional Pearl: A Smart View on Datatypes},
booktitle = {Proceedings of the 20th {ACM} {SIGPLAN} International Conference on Functional Programming},
pages     = {355--361},
editor    = {Kathleen Fisher and John H. Reppy},
location  = {Vancouver, Canada},
url       = {http://doi.acm.org/10.1145/2784731.2784743},
doi       = {10.1145/2784731.2784743},
year      = {2015}

 author     = {Jaskelioff, Mauro and Rivas, Exequiel},
 title      = {Functional Pearl: A Smart View on Datatypes},
 journal    = {SIGPLAN Not.},
 issue_date = {September 2015},
 volume     = {50},
 number     = {9},
 month      = aug,
 year       = {2015},
 issn       = {0362-1340},
 pages      = {355--361},
 numpages   = {7},
 url        = {http://doi.acm.org/10.1145/2858949.2784743},
 doi        = {10.1145/2858949.2784743},
 publisher  = {ACM},
 address    = {New York, NY, USA},
 keywords   = {Data Structure, List, Monad, MonadPlus},