Proving equivalence between non-tail-recursive and tail-recursive functions

Question

I have a recursive function* that is similar to an "optional map", with the following signature:

omap (f : option Z -> list nat) (l : list Z) : option (list nat)

I defined an equivalent (modulo list reversal) tail-recursive function (omap_tr below), and I would like to prove that both are equivalent, at least in the case Some.

I am currently failing to do so, either because my inductive invariant is not strong enough, or because I am not correctly applying the double induction. I wonder if there is a standard technique for this kind of transformation.

*The function has been simplified; for instance None seems useless here, but it is necessary in the original function.

Code

Here is the code of the (simplified) non-tail-recursive function, along with an example of a function f:

Fixpoint omap (f : option Z -> list nat) (l : list Z) : option (list nat) :=
  match l with
  | nil => Some nil
  | z :: zr =>
    let nr1 := f (Some z) in
    let nr2 := match omap f zr with
               | None => nil
               | Some nr' => nr'
               end in
    Some (nr1 ++ nr2)
  end.

Let f (oz : option Z) : list nat :=
  match oz with
  | None => nil
  | Some z => Z.to_nat z :: nil
  end.

For instance, omap f simply converts Z integers to nat integers:

Compute omap f (1 :: 2 :: 3 :: 4 :: nil)%Z.

= Some (1%nat :: 2%nat :: 3%nat :: 4%nat :: nil)  : option (list nat)

I performed what I believe is a standard accumulator-based transformation, adding an acc parameter to both f and omap:

Fixpoint omap_tr (f_tr : option Z -> list nat -> list nat) (l : list Z)
                 (acc : list nat) : option (list nat) :=
  match l with
  | nil => Some acc
  | z :: zr => let nr1 := f_tr (Some z) acc in
               omap_tr f_tr zr nr1
  end.

Let f_tr rz acc :=
  match rz with
  | None => acc
  | Some z => Z.to_nat z :: acc
  end.

It seems to work, despite returning a reversed list. Here's an example of its usage, with a non-empty accumulator:

Compute match omap_tr f_tr (3 :: 4 :: nil)%Z (rev (1 :: 2 :: nil))%nat with
          | Some r => Some (rev r)
          | None => None
        end.

= Some (1%nat :: 2%nat :: 3%nat :: 4%nat :: nil)  : option (list nat)

My first attempt included a nil accumulator:

Lemma omap_tr_failed:
  forall l res,
    omap_tr f_tr l nil = Some res ->
    omap f l = Some (rev res).

But I failed to do the induction. I assume it must be because the invariant is not strong enough to handle the general case.

Still, it seems to me that any of the following lemmas should be provable, but I'm afraid they are also not strong enough to enable the proof:

Lemma omap_tr':
  forall l acc res,
    omap_tr f_tr l acc = Some (res ++ acc) ->
    omap f l = Some (rev res).

Lemma omap_tr'':
  forall l acc res,
    omap_tr f_tr l acc = Some res ->
    exists res',
      omap f l = Some res' /\
      res = (rev res') ++ acc.

Should a standard double induction allow these lemmas to be proven directly, or do I need stronger invariants?

Arthur Azevedo De Amorim Arthur Azevedo De Amorim · Accepted Answer · 2015-04-16T20:47:38

Yes, your omap_tr'' invariant works perfectly for your lemma. Maybe you forgot to generalize over acc and res before doing induction, or forgot to apply some rewriting facts about app and rev?

Lemma omap_tr'':
  forall l acc res,
    omap_tr f_tr l acc = Some res ->
    exists res',
      omap f l = Some res' /\
      res = (rev res') ++ acc.
Proof.
  induction l as [|x l IH]; intros acc res; simpl.
  - intros H. inversion H; subst acc; clear H.
    exists []; eauto.
  - intros H. apply IH in H.
    destruct H as (res' & H & ?). subst res.
    rewrite H.
    eexists; split; eauto.
    simpl. now rewrite <- app_assoc.
Qed.

Lemma omap_tr_correct :
  forall l res,
    omap_tr f_tr l [] = Some res ->
    omap f l = Some (rev res).
Proof.
  intros l res H. apply omap_tr'' in H.
  destruct H as (res' & ? & E).
  subst res.
  now rewrite app_nil_r, rev_involutive.
Qed.

Proving equivalence between non-tail-recursive and tail-recursive functions

Code

1 Answers