A case study on algorithm discovery from proofs: The insert function on binary trees

摘要

We present a proof-based automatic synthesis experiment in the context of sorting binary trees, namely the synthesis of the function which inserts an element in a sorted binary tree at the appropriate place. The algorithm is automatically extracted from the automatically produced proof of the conjecture which expresses the existence of the desired output for each appropriate input of the function.