Shapeliness analysis of functional programs with algebraic data types

Data distribution algebras are an abstract notion for the description of parallel programs. Their dynamic execution can be optimized if they are shapely. In this paper we describe a shape analysis which allows compile-time shapeliness-tests. It operates on the structure of algebraic data types and works for arbitrary functional programs rather than only shapely ones. Besides a first-order calculus we also propose a higher-order version which can handle higher-order functions as well.