Recursion Schemes in Coq

Program calculation, a programming technique to derive efficient programs from naive ones by program transformation, is challenging for program optimization. Tesson et al. have shown that Coq, a popular proof assistant, provides a cost-effective way to implement a powerful system for verifying correctness of program transformations, but their applications are limited to list functions in the Theory of Lists. In this paper, we propose an easy-to-use Coq library to prove more advanced calculation rules in Coq for various recursion schemes, which capture recursive programs on an arbitrary algebraic datatype. We prove all the lemmas and theorems about recursion schemes in Coq including histomorphisms and futumorphisms proposed by Uustalu et al. Our library can be used to obtain certified runnable programs from their definitions written with recursion schemes in Coq scripts. We demonstrate a certified runnable program for the Fibonacci numbers and unbounded knapsack problem from their histomorphic definitions.