%O Report 
%F jpzh2002
%A Jha, Sian
%A Palsberg, Jens
%A Zhao, Tian
%A Henglein, Fritz
%T Efficient Type Matching
%I Department of Computer Science, University of Copenhagen (DIKU)
%X Palsberg and Zhao presented an $O(n^2)$ time algorithm for matching two recursive types; that is, deciding type isomorphism under associative-commutative type constructors. In this paper, we present an $O(n \log n)$ algorithm for matching recursive types and an $O(n)$ algorithm for matching nonrecursive types. The linear-time algorithm for nonrecursive types works without hashing or pointer arithmetic, by employing multiset discrimination due to Paige {\it et al.}. The $O(n \log n)$ algorithm for recursive types works by reducing the type matching problem to the problem of finding a size-stable partition of a graph, which has $O(n \log n)$ algorithms due to Cardon/Crochemore and Paige/Tarjan. The key to these algorithms is the use of a ``modify-the-smaller-half'' approach pioneered by Hopcroft and Ullman for DFA minimization. Our results may help improve systems, such as Polyspin and Mockingbird, that are designed to facilitate interoperability of software components. We also discuss possible applications of our algorithm to {\tt\small Java}. Issues related to subtyping of recursive types are also discussed
%U http://www.diku.dk/hjemmesider/ansatte/henglein/papers/jha2002.pdf
%D 2002
%K rectype
%K  parametricity