The present paper shows how the idea of equality saturation can be used to prove algebraic properties of programs written in a non-total non-strict first-order functional language. We adapt equality saturation approach to a functional language by using transformations borrowed mainly from supercompilation. Proof by induction is performed via a special transformation called merging by bisimilarity. We compare our experimental prover based on this method with a supercompiler HOSC and inductive provers HipSpec and Zeno.
['Sergei Alexandrovich Grechanik']
Proving properties of functional programs by equality saturation