Square matrices serve as an interesting case study in functional programmign.common representations,such as lists of liss,are both inefficietn-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 seocnd.We devleop a represetnaiton that solves both problems: it offers logarithmic access to each individual eelment and t captures the shape invariants in the tyep,where they cna be checked by the ocmpiler.One interesting feature of our solution is that it translates the well-known fast exponentiation aloirthm 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.
展开▼
