A novel representation of lists and its application to the function “reverse” Export

@article{citeulike:5904885, abstract = {A representation of lists as first-class functions is proposed. Lists represented in this way can be appended together in constant time, and can be converted back into ordinary lists in time proportional to their length. Programs which construct lists using append can often be improved by using this representation. For example, naive reverse can be made to run in linear time, and the conventional 'fast reverse' can then be derived easily. Examples are given in KRC (Turner, 1982), the notation being explained as it is introduced. The method can be compared to Sleep and Holmstr\"{o}m's proposal (1982) to achieve a similar effect by a change to the interpreter.}, author = {Hughes}, citeulike-article-id = {5904885}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0020-0190(86)90059-1}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/0020-0190(86)90059-1}, citeulike-linkout-2 = {http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf}, day = {03}, doi = {10.1016/0020-0190(86)90059-1}, issn = {00200190}, journal = {Information Processing Letters}, keywords = {data-structures, functional-programming, krc, lists}, month = {March}, number = {3}, pages = {141--144}, posted-at = {2009-10-07 10:53:58}, priority = {2}, title = {A novel representation of lists and its application to the function ” reverse”}, url = {http://dx.doi.org/10.1016/0020-0190(86)90059-1}, volume = {22}, year = {1986} }

TY - JOUR ID - citeulike:5904885 L3 - citeulike-article-id:5904885 N2 - A representation of lists as first-class functions is proposed. Lists represented in this way can be appended together in constant time, and can be converted back into ordinary lists in time proportional to their length. Programs which construct lists using append can often be improved by using this representation. For example, naive reverse can be made to run in linear time, and the conventional ‘fast reverse’ can then be derived easily. Examples are given in KRC (Turner, 1982), the notation being explained as it is introduced. The method can be compared to Sleep and Holmström's proposal (1982) to achieve a similar effect by a change to the interpreter. IS - 3 JF - Information Processing Letters SN - 00200190 EP - 144 TI - A novel representation of lists and its application to the function “reverse” VL - 22 SP - 141 KW - data-structures KW - functional-programming KW - krc KW - lists AU - Hughes PY - 1986/03/03/ UR - http://dx.doi.org/10.1016/0020-0190(86)90059-1 ER -