Generic discrimination: sorting and paritioning unshared data in linear time

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.

We give some examples of the uses of discriminators, including a new most-significant-digit lexicographic sorting algorithm.

Discriminators generalize binary comparison functions: They operate on n arguments at a time, but do not expose more information than the underlying equivalence, respectively ordering relation on the arguments. We argue that primitive types with equality (such as references in ML) and ordered types (such as the machine integer type), should expose their equality, respectively standard ordering relation, as discriminators: Having only a binary equality test on a type requires Θ(n²) time to find all the occurrences of an element in a list of length n, for each element in the list, even if the equality test takes only constant time. A discriminator accomplishes this in linear time. Likewise, having only a (constant-time) comparison function requires Θ(n log n) time to sort a list of n elements. A discriminator can do this in linear time.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 2: Thomas Ambus. Multiset discrimination for internal and external data management. Master's thesis, DIKU, University of Copenhagen, July 2004. http://plan-x.org/projects/msd/msd.pdf.
• 3: A. Andersson , S. Nilsson, A new efficient radix sort, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.714-721, November 20-22, 1994 [doi>10.1109/SFCS.1994.365721]
• 4: Arne Andersson , Stefan Nilsson, Implementing radixsort, Journal of Experimental Algorithmics (JEA), 3, p.7-es, 1998 [doi>10.1145/297096.297136]
• 5: Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Journal of Computer and System Sciences, v.57 n.1, p.74-93, Aug. 1998 [doi>10.1006/jcss.1998.1580]
• 6: K. E. Batcher. Sorting networks and their applications. In Proc. AFIPS Spring Joint Computer Conference, volume 32, pages 307--314, 1968.
• 7: Jon Bentley, Programming pearls: Aha algorithms, Communications of the ACM, v.26 n.9, p.623-628, Sept. 1983 [doi>10.1145/358172.358176]
• 8: Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99605]
• 9: Jiazhen Cai , Robert Paige, Using multiset discrimination to solve language processing problems without hashing, Theoretical Computer Science, v.145 n.1-2, p.189-228, July 10, 1995 [doi>10.1016/0304-3975(94)00183-J]
• 10: Gianni Franceschini, S. Muthukrishnan, and Mihai Patrascu. Radix sorting with no extra space. In Proc. European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science (LNCS), pages 194--205. Springer, 2007. doi: 10.1007/978-3-540-75520-3.
• 11: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 12: Glasgow Haskell. The Glasgow Haskell Compiler. http://www.haskell.org/ghc/, 2005.
• 13: Yijie Han , Mikkel Thorup, Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.135-144, November 16-19, 2002
• 14: Fritz Henglein. Multiset discrimination. Unpublished manuscript. See http://plan-x.org/msd/multiset-discrimination.pdf, September 2003.
• 15: Fritz Henglein. A language for total preorders. Unfinished manuscript, March 2008.
• 16: Fritz Henglein , Jesper Jørgensen, Formally optimal boxing, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-226, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177874]
• 17: Ralf Hinze, Generalizing generalized tries, Journal of Functional Programming, v.10 n.4, p.327-351, July 2000 [doi>10.1017/S0956796800003713]
• 18: C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
• 19: Johan Jeuring , Patrik Jansson, Polytypic Programming, Advanced Functional Programming, Second International School-Tutorial Text, p.68-114, August 26-30, 1996
• 20: Sian Jha, Jens Palsberg, Tian Zhao, and Fritz Henglein. Efficient type matching. In Olivier Danvy, Fritz Henglein, Harry Mairson, and Alberto Pettorossi, editors, Automatic Program Development-A Tribute to Robert Paige. Springer, 2008. ISBN 978-1-4020-6584-2.
• 21: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 22: Kurt Mehlhorn, Sorting and Searching (Eatcs Monographs on Theoretical Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 1984
• 23: R. Paige. Optimal translation of user input in dynamically typed languages. Draft, July 1991.
• 24: Robert Paige. Efficient translation of external input in a dynamically typed language. In Proc. 13th World Computer Congress. Elsevier, February 1994.
• 25: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• 26: Robert Paige , Zhe Yang, High level reading and data structure compilation, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.456-469, January 15-17, 1997, Paris, France [doi>10.1145/263699.263762]
• 27: D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
• 28: Ranjan Sinha , Justin Zobel, Efficient trie-based sorting of large sets of strings, Proceedings of the 26th Australasian computer science conference, p.11-18, February 01, 2003, Adelaide, Australia
• 29: J. W. J. Williams. Algorithm 232 - heapsort. Communications of the ACM, 7(6):347--348, 1964.
• 30: Yoav Zibin , Joseph (Yossi) Gil , Jeffrey Considine, Efficient algorithms for isomorphisms of simple types, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.160-171, January 15-17, 2003, New Orleans, Louisiana, USA

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Algorithms, Languages, Theory

Keywords:
discrimination, discriminator, equivalence, functional, generic, multiset discrimination, order, partitioning, sorting, total preorder