Minimally Strict Polymorphic Functions

In this paper we show how to efficiently check whether a polymorphic function is minimally strict. A function is minimally strict if it is the minimal element of a specific less-strict ordering. We prove that we can check whether two polymorphic functions are related by the less-strict ordering by either checking it a) for an arbitrary monomorphic instance of the functions or b) for all shapes of the functions’ argument type. A shape is a value of a monomorphic instance of a polymorphic data type where each polymorphic component is replaced by an element that identifies its position in the data structure. In contrast to recent publications that characterize polymorphic functions by monomorphic instances we consider non-termination and selective strictness, i.e., a language closer to Haskell.