Coq - use Prop (True | False) in if ... then ... else

Question

I'm kind of new to Coq.

I'm trying to implement a generic version of insertion sort. I'm implementing is as a module that takes a Comparator as a parameter. This Comparator implements comparison operators (such as is_eq, is_le, is_neq, etc.).

In insertion sort, in order to insert, I must compare two elements in the input list, and based on the result of the comparison, insert the element into the correct location.

My problem is that the implementations of the comparison operators are type -> type -> prop (i need them to be like this for implementation of other types/proofs). I'd rather not create type -> type -> bool versions of the operators if it can be avoided.

Is there any way to convert a True | False prop to a bool for use in a if ... then ... else clause?

The comparator module type:

Module Type ComparatorSig.

  Parameter X: Set.
  Parameter is_eq : X -> X -> Prop.
  Parameter is_le : X -> X -> Prop.
  Parameter is_neq :  X -> X -> Prop.

  Infix "=" := is_eq (at level 70).
  Infix "<>" := (~ is_eq) (at level 70).
  Infix "<=" := is_le (at level 70).

  Parameter eqDec : forall x y : X, { x = y } + { x <> y }.

  Axiom is_le_trans : forall (x y z:X), is_le x y -> is_le y z -> is_le x z.

End ComparatorSig.

An implementation for natural numbers:

Module IntComparator <: Comparator.ComparatorSig.
  Definition X := nat.
  Definition is_le x y := x <= y.
  Definition is_eq x y := eq_nat x y.
  Definition is_neq x y:= ~ is_eq  x y.

  Definition eqDec := eq_nat_dec.

  Definition is_le_trans := le_trans.
End IntComparator.

The insertion part of insertion sort:

  Fixpoint insert (x : IntComparator .X) (l : list IntComparator .X) :=
    match l with
      | nil => x :: nil
      | h :: tl => if IntComparator.is_le x h then x :: h :: tl else h :: (insert x tl)
    end.

(obviously, the insert fixpoint doesn't work, since is_le is returns Prop and not bool).

Any help is appreciated.

Answer 1

You seem to be a bit confused about Prop.

is_le x y is of type Prop, and is the statement x is less or equal to y. It is not a proof that this statement is correct. A proof that this statement is correct would be p : is_le x y, an inhabitant of that type (i.e. a witness of that statement's truth).

This is why it does not make much sense to pattern match on IntComparator.is_le x h.

A better interface would be the following:

Module Type ComparatorSig.

  Parameter X: Set.
  Parameter is_le : X -> X -> Prop.
  Parameter is_le_dec : forall x y, { is_le x y } + { ~ is_le x y }.

In particular, the type of is_le_dec is that of a decision procedure for the property is_le, that is, it returns either a proof that x <= y, or a proof that ~ (x <= y). Since this is a type with two constructors, you can leverage the if sugar:

... (if IntComparator.is_le_dec x h then ... else ...) ...

This is, in some sense, an enhanced bool, which returns a witness for what it is trying to decide. The type in question is called sumbool and you can learn about it here: http://coq.inria.fr/library/Coq.Init.Specif.html#sumbool

---

In general, it does not make sense to talk about True or False in executing code.

First, because these live in Prop, which means that they cannot be computationally relevant as they will be erased.

Second, because they are not the only inhabitants of Prop. While true and false are the only values of type bool, which implies you can pattern-match, the type Prop contains an infinite number of elements (all the statements you can imagine), thus it makes no sense to try and pattern-match on a element of type Prop.