  Dependently typed programming languages allow sophisticated properties of
data to be expressed within the type system. Of particular use in dependently
typed programming are indexed types that refine data by computationally useful
information. For example, the N-indexed type of vectors refines lists by their
lengths. Other data types may be refined in similar ways, but programmers must
produce purpose-specific refinements on an ad hoc basis, developers must
anticipate which refinements to include in libraries, and implementations must
often store redundant information about data and their refinements. In this
paper we show how to generically derive inductive characterisations of
refinements of inductive types, and argue that these characterisations can
alleviate some of the aforementioned difficulties associated with ad hoc
refinements. Our characterisations also ensure that standard techniques for
programming with and reasoning about inductive types are applicable to
refinements, and that refinements can themselves be further refined.
