ComputingComputer ScienceFormal MethodsProgramming LanguagesSyntaxAbstract Syntax TreesData TypesGeneric ProgrammingType CheckingType SystemsAgdaConstructorsPolymorphic Type SystemsPolymorphic TypesType ClassesType ConstructorsType PolymorphismType Theory
We show that the syntactically rich notion of inductive families can be reduced to a core type theory with a fixed number of type constructors exploiting the novel notion of indexed containers. Indexed containers generalize simple containers, capturing strictly positive families instead of just strictly positive types, without having to extend the core type theory. Other applications of indexed containers include data type-generic programming and reasoning about polymorphic functions. The construction presented here has been formalized using the Agda system.
11
Gérard Huet · Journal of Functional Programming · 1997 · 310 citations
James Cheney, Ralf Hinze · eCommons (Cornell University) · 2003 · 180 citations · Full text
Normal functors, power series and λ-calculus
Jean-Yves Girard · Annals of Pure and Applied Logic · 1988 · 123 citations
Thorsten Altenkirch, Conor McBride, Wouter Swierstra · 2007 · 120 citations