Chris Okasaki
ABSTRACT
Square matrices serve as an interesting case study in functional programming. Common representations, such as lists of lists, are both inefficient---at least for access to individual elements---and error-prone, because the compiler cannot enforce "squareness". Switching to a typical balanced-tree representation solves the first problem, but not the second. We develop a representation that solves both problems: it offers logarithmic access to each individual element and it captures the shape invariants in the type, where they can be checked by the compiler. One interesting feature of our solution is that it translates the well-known fast exponentiation algorithm to the level of types. Our implementation also provides a stress test for today's advanced type systems---it uses nested types, polymorphic recursion, higher-order kinds, and rank-2 polymorphism.
- 1.Richard S. Bird and Lambert Meertens. Nested datatypes. In Conference on Mathematics of Program Construction, volume 1422 of LNCS, June 1998. Google Scholar
Digital Library
- 2.Richard S. Bird and Ross Paterson. de Bruijn notation as a nested datatype. Journal of Functional Programming, To appear. Google ScholarDigital Library
- 3.F. Warren Burton and John G. Kollias. Functional programming with quadtrees. IEEE Software, 6(1):90- 97, January 1989. Google ScholarDigital Library
- 4.Jeremy D. Frens and David S. Wise. Matrix inversion using quadtrees implemented in gofer. Technical Report 433, Computer Science Department, Indiana University, May 1995.Google Scholar
- 5.Fritz Henglein. Type inference with polymorphic recursion. A CM Transactions on Programming Languages and Systems, 15(2):253-289, April 1993. Google ScholarDigital Library
- 6.Ratf Hinze. Polytypic functions over nested datatypes (extended abstract). In Latin-American Conference on Functional Programming, March 1999.Google Scholar
- 7.Anne KaJdewaij and Victor J. Dielissen. Leaf trees. Science of Computer Programming, 26(1-3): 149-165, May 1996. Google ScholarDigital Library
- 8.Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998. Google ScholarDigital Library
- 9.Simon Peyton Jones et al. Haskell 98: A non-strict, purely functional language. http://haskell, org/onlinereport/, February 1999.Google Scholar
- 10.Hanan Samet. The quadtree and related hierarchical data structures. A CM Computing Surveys, 16(2):187- 260, June 1984. Google ScholarDigital Library
- 11.David S. Wise. Matrix algorithms using quadtrees. Technical Report 357, Computer Science Department, Indiana University, June 1992.Google Scholar
Index Terms
- From fast exponentiation to square matrices: an adventure in types
Recommendations
From fast exponentiation to square matrices: an adventure in types
Square matrices serve as an interesting case study in functional programming. Common representations, such as lists of lists, are both inefficient---at least for access to individual elements---and error-prone, because the compiler cannot enforce "...
Total positivity of Narayana matrices
We prove the total positivity of the Narayana triangles of type A and type B, and thus affirmatively confirm a conjecture of Chen, Liang and Wang and a conjecture of Pan and Zeng. We also prove the strict total positivity of the Narayana squares of type ...
A Fast Solver for HSS Representations via Sparse Matrices
In this paper we present a fast direct solver for certain classes of dense structured linear systems that works by first converting the given dense system to a larger system of block sparse equations and then uses standard sparse direct solvers. The ...
Comments