Coq: Error: The reference _ was not found in the current environment

Question

I'm new to Coq. I'm having trouble defining lists, maps, and trees using units, products, and sums. I get the error message in the title. The code above the comment works fine, the code below it does not.

Inductive one : Type := nil : one.

Inductive sum (t0 t1 : Type) : Type :=
  | inject_left : t0 -> sum t0 t1
  | inject_right : t1 -> sum t0 t1.

Inductive product (t0 t1 : Type) : Type := pair : t0 -> t1 -> product t0 t1.

Definition list (t0 : Type) : Type := sum one (product t0 (list t0)).

Definition map (t0 t1 : Type) : Type := list (product t0 t1).

(* From here on nothing works. *)

Definition List (t0 : Type) : Type := sum one (product t0 (List t0)).

Definition map (t0 t1 : Type) : Type :=
  sum one (product (product t0 t1) (map t0 t1)).

Definition Map (t0 t1 : Type) : Type :=
  sum one (product (product t0 t1) (Map t0 t1)).

Definition tree (t0 : Type) : Type :=
  sum one (product t0 (product (tree t0) (tree t0))).

Definition Tree (t0 : Type) : Type :=
  sum one (product t0 (product (Tree t0) (Tree t0))).

Looking back, I'm guessing the definition of list worked only because it's already implicitly imported. I guess I need to use Inductive to define recursive types. — user1494846

Ptival Ptival · Accepted Answer · 2012-07-02T05:24:19

Definition List (t0 : Type) : Type := sum one (product t0 (List t0)).

In Coq, you cannot write a recursive function by using Definition, you need to use Fixpoint (or something stronger). See http://coq.inria.fr/refman/Reference-Manual003.html#@command14

Now, that's not all, but a recursive definition has to be provably-terminating (to ensure consistency of the logic you use). In particular, you cannot write something like:

Fixpoint List (t0 : Type) : Type := sum one (product t0 (List t0)).

Since you're doing a recursive call on the same argument you got in. This obviously fails to terminate.

Anyway, to define types like these, you should probably rather use Inductive (and CoInductive), as you already figured out.

Coq: Error: The reference _ was not found in the current environment

1 Answers