adam@286: (* Copyright (c) 2008-2010, Adam Chlipala
adamc@193:  * 
adamc@193:  * This work is licensed under a
adamc@193:  * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
adamc@193:  * Unported License.
adamc@193:  * The license text is available at:
adamc@193:  *   http://creativecommons.org/licenses/by-nc-nd/3.0/
adamc@193:  *)
adamc@193: 
adamc@193: (* begin hide *)
adamc@195: Require Import String List.
adamc@193: 
adam@314: Require Import CpdtTactics DepList.
adamc@193: 
adamc@193: Set Implicit Arguments.
adamc@193: (* end hide *)
adamc@193: 
adamc@193: 
adamc@219: (** %\chapter{Generic Programming}% *)
adamc@193: 
adam@358: (** %\index{generic programming}\textit{%#<i>#Generic programming#</i>#%}% makes it possible to write functions that operate over different types of data.  %\index{parametric polymorphism}%Parametric polymorphism in ML and Haskell is one of the simplest examples.  ML-style %\index{module systems}%module systems%~\cite{modules}% and Haskell %\index{type classes}%type classes%~\cite{typeclasses}% are more flexible cases.  These language features are often not as powerful as we would like.  For instance, while Haskell includes a type class classifying those types whose values can be pretty-printed, per-type pretty-printing is usually either implemented manually or implemented via a %\index{deriving clauses}%[deriving] clause, which triggers ad-hoc code generation.  Some clever encoding tricks have been used to achieve better within Haskell and other languages, but we can do %\index{datatype-generic programming}\emph{%#<i>#datatype-generic programming#</i>#%}% much more cleanly with dependent types.  Thanks to the expressive power of CIC, we need no special language support.
adamc@193: 
adamc@219:    Generic programming can often be very useful in Coq developments, so we devote this chapter to studying it.  In a proof assistant, there is the new possibility of generic proofs about generic programs, which we also devote some space to. *)
adamc@193: 
adamc@195: (** * Reflecting Datatype Definitions *)
adamc@193: 
adam@358: (** The key to generic programming with dependent types is %\index{universe types}\textit{%#<i>#universe types#</i>#%}%.  This concept should not be confused with the idea of %\textit{%#<i>#universes#</i>#%}% from the metatheory of CIC and related languages.  Rather, the idea of universe types is to define inductive types that provide %\textit{%#<i>#syntactic representations#</i>#%}% of Coq types.  We cannot directly write CIC programs that do case analysis on types, but we %\textit{%#<i>#can#</i>#%}% case analyze on reflected syntactic versions of those types.
adamc@219: 
adam@358:    Thus, to begin, we must define a syntactic representation of some class of datatypes.  In this chapter, our running example will have to do with basic algebraic datatypes, of the kind found in ML and Haskell, but without additional bells and whistles like type parameters and mutually recursive definitions.
adamc@219: 
adamc@219:    The first step is to define a representation for constructors of our datatypes. *)
adamc@219: 
adamc@198: (* EX: Define a reflected representation of simple algebraic datatypes. *)
adamc@198: 
adamc@198: (* begin thide *)
adamc@193: Record constructor : Type := Con {
adamc@193:   nonrecursive : Type;
adamc@193:   recursive : nat
adamc@193: }.
adamc@193: 
adam@286: (** The idea is that a constructor represented as [Con T n] has [n] arguments of the type that we are defining.  Additionally, all of the other, non-recursive arguments can be encoded in the type [T].  When there are no non-recursive arguments, [T] can be [unit].  When there are two non-recursive arguments, of types [A] and [B], [T] can be [A * B].  We can generalize to any number of arguments via tupling.
adamc@219: 
adamc@219:    With this definition, it as easy to define a datatype representation in terms of lists of constructors. *)
adamc@219: 
adamc@193: Definition datatype := list constructor.
adamc@193: 
adamc@219: (** Here are a few example encodings for some common types from the Coq standard library.  While our syntax type does not support type parameters directly, we can implement them at the meta level, via functions from types to [datatype]s. *)
adamc@219: 
adamc@193: Definition Empty_set_dt : datatype := nil.
adamc@193: Definition unit_dt : datatype := Con unit 0 :: nil.
adamc@193: Definition bool_dt : datatype := Con unit 0 :: Con unit 0 :: nil.
adamc@193: Definition nat_dt : datatype := Con unit 0 :: Con unit 1 :: nil.
adamc@193: Definition list_dt (A : Type) : datatype := Con unit 0 :: Con A 1 :: nil.
adamc@219: 
adam@358: (** The type [Empty_set] has no constructors, so its representation is the empty list.  The type [unit] has one constructor with no arguments, so its one reflected constructor indicates no non-recursive data and [0] recursive arguments.  The representation for [bool] just duplicates this single argumentless constructor.    We get from [bool] to [nat] by changing one of the constructors to indicate 1 recursive argument.  We get from [nat] to [list] by adding a non-recursive argument of a parameter type [A].
adamc@219: 
adamc@219:    As a further example, we can do the same encoding for a generic binary tree type. *)
adamc@219: 
adamc@198: (* end thide *)
adamc@193: 
adamc@193: Section tree.
adamc@193:   Variable A : Type.
adamc@193: 
adamc@193:   Inductive tree : Type :=
adamc@193:   | Leaf : A -> tree
adamc@193:   | Node : tree -> tree -> tree.
adamc@193: End tree.
adamc@193: 
adamc@198: (* begin thide *)
adamc@193: Definition tree_dt (A : Type) : datatype := Con A 0 :: Con unit 2 :: nil.
adamc@193: 
adamc@219: (** Each datatype representation stands for a family of inductive types.  For a specific real datatype and a reputed representation for it, it is useful to define a type of %\textit{%#<i>#evidence#</i>#%}% that the datatype is compatible with the encoding. *)
adamc@219: 
adamc@193: Section denote.
adamc@193:   Variable T : Type.
adamc@219:   (** This variable stands for the concrete datatype that we are interested in. *)
adamc@193: 
adamc@193:   Definition constructorDenote (c : constructor) :=
adamc@193:     nonrecursive c -> ilist T (recursive c) -> T.
adam@358:   (** We write that a constructor is represented as a function returning a [T].  Such a function takes two arguments, which pack together the non-recursive and recursive arguments of the constructor.  We represent a tuple of all recursive arguments using the length-indexed list type %\index{Gallina terms!ilist}%[ilist] that we met in Chapter 8. *)
adamc@193: 
adamc@193:   Definition datatypeDenote := hlist constructorDenote.
adam@358:   (** Finally, the evidence for type [T] is a %\index{Gallina terms!hlist}%heterogeneous list, including a constructor denotation for every constructor encoding in a datatype encoding.  Recall that, since we are inside a section binding [T] as a variable, [constructorDenote] is automatically parameterized by [T]. *)
adamc@219: 
adamc@193: End denote.
adamc@198: (* end thide *)
adamc@193: 
adamc@219: (** Some example pieces of evidence should help clarify the convention.  First, we define some helpful notations, providing different ways of writing constructor denotations.  There is really just one notation, but we need several versions of it to cover different choices of which variables will be used in the body of a definition.  %The ASCII \texttt{\textasciitilde{}>} from the notation will be rendered later as $\leadsto$.% *)
adamc@219: 
adamc@219: (** printing ~> $\leadsto$ *)
adamc@219: 
adamc@193: Notation "[ ! , ! ~> x ]" := ((fun _ _ => x) : constructorDenote _ (Con _ _)).
adamc@193: Notation "[ v , ! ~> x ]" := ((fun v _ => x) : constructorDenote _ (Con _ _)).
adamc@219: Notation "[ ! , r ~> x ]" := ((fun _ r => x) : constructorDenote _ (Con _ _)).
adamc@219: Notation "[ v , r ~> x ]" := ((fun v r => x) : constructorDenote _ (Con _ _)).
adamc@193: 
adamc@198: (* begin thide *)
adamc@193: Definition Empty_set_den : datatypeDenote Empty_set Empty_set_dt :=
adamc@216:   HNil.
adamc@193: Definition unit_den : datatypeDenote unit unit_dt :=
adamc@216:   [!, ! ~> tt] ::: HNil.
adamc@193: Definition bool_den : datatypeDenote bool bool_dt :=
adamc@216:   [!, ! ~> true] ::: [!, ! ~> false] ::: HNil.
adamc@193: Definition nat_den : datatypeDenote nat nat_dt :=
adamc@219:   [!, ! ~> O] ::: [!, r ~> S (hd r)] ::: HNil.
adamc@193: Definition list_den (A : Type) : datatypeDenote (list A) (list_dt A) :=
adamc@219:   [!, ! ~> nil] ::: [x, r ~> x :: hd r] ::: HNil.
adamc@193: Definition tree_den (A : Type) : datatypeDenote (tree A) (tree_dt A) :=
adamc@219:   [v, ! ~> Leaf v] ::: [!, r ~> Node (hd r) (hd (tl r))] ::: HNil.
adamc@198: (* end thide *)
adamc@194: 
adam@358: (** Recall that the [hd] and [tl] calls above operate on richly typed lists, where type indices tell us the lengths of lists, guaranteeing the safety of operations like [hd].  The type annotation attached to each definition provides enough information for Coq to infer list lengths at appropriate points. *)
adam@358: 
adamc@195: 
adamc@195: (** * Recursive Definitions *)
adamc@195: 
adamc@198: (* EX: Define a generic [size] function. *)
adamc@198: 
adam@358: (** We built these encodings of datatypes to help us write datatype-generic recursive functions.  To do so, we will want a reflected representation of a %\index{recursion schemes}\textit{%#<i>#recursion scheme#</i>#%}% for each type, similar to the [T_rect] principle generated automatically for an inductive definition of [T].  A clever reuse of [datatypeDenote] yields a short definition. *)
adamc@219: 
adamc@198: (* begin thide *)
adamc@194: Definition fixDenote (T : Type) (dt : datatype) :=
adamc@194:   forall (R : Type), datatypeDenote R dt -> (T -> R).
adamc@194: 
adamc@219: (** The idea of a recursion scheme is parameterized by a type and a reputed encoding of it.  The principle itself is polymorphic in a type [R], which is the return type of the recursive function that we mean to write.  The next argument is a hetergeneous list of one case of the recursive function definition for each datatype constructor.  The [datatypeDenote] function turns out to have just the right definition to express the type we need; a set of function cases is just like an alternate set of constructors where we replace the original type [T] with the function result type [R].  Given such a reflected definition, a [fixDenote] invocation returns a function from [T] to [R], which is just what we wanted.
adamc@219: 
adamc@219:    We are ready to write some example functions now.  It will be useful to use one new function from the [DepList] library included in the book source. *)
adamc@219: 
adamc@219: Check hmake.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:   hmake
adamc@219:      : forall (A : Type) (B : A -> Type),
adam@358:        (forall x : A, B x) -> forall ls : list A, hlist B ls
adamc@219:        ]]
adamc@219: 
adam@358:   The function [hmake] is a kind of [map] alternative that goes from a regular [list] to an [hlist].  We can use it to define a generic size function that counts the number of constructors used to build a value in a datatype. *)
adamc@219: 
adamc@194: Definition size T dt (fx : fixDenote T dt) : T -> nat :=
adamc@194:   fx nat (hmake (B := constructorDenote nat) (fun _ _ r => foldr plus 1 r) dt).
adamc@194: 
adamc@219: (** Our definition is parameterized over a recursion scheme [fx].  We instantiate [fx] by passing it the function result type and a set of function cases, where we build the latter with [hmake].  The function argument to [hmake] takes three arguments: the representation of a constructor, its non-recursive arguments, and the results of recursive calls on all of its recursive arguments.  We only need the recursive call results here, so we call them [r] and bind the other two inputs with wildcards.  The actual case body is simple: we add together the recursive call results and increment the result by one (to account for the current constructor).  This [foldr] function is an [hlist]-specific version defined in the [DepList] module.
adamc@219: 
adamc@219:    It is instructive to build [fixDenote] values for our example types and see what specialized [size] functions result from them. *)
adamc@219: 
adamc@194: Definition Empty_set_fix : fixDenote Empty_set Empty_set_dt :=
adamc@194:   fun R _ emp => match emp with end.
adamc@194: Eval compute in size Empty_set_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun emp : Empty_set => match emp return nat with
adamc@219:                               end
adamc@219:      : Empty_set -> nat
adamc@219: ]]
adamc@219: 
adamc@219: Despite all the fanciness of the generic [size] function, CIC's standard computation rules suffice to normalize the generic function specialization to exactly what we would have written manually. *)
adamc@194: 
adamc@194: Definition unit_fix : fixDenote unit unit_dt :=
adamc@216:   fun R cases _ => (hhd cases) tt INil.
adamc@194: Eval compute in size unit_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun _ : unit => 1
adamc@219:      : unit -> nat
adamc@219: ]]
adamc@219: 
adamc@219: Again normalization gives us the natural function definition.  We see this pattern repeated for our other example types. *)
adamc@194: 
adamc@194: Definition bool_fix : fixDenote bool bool_dt :=
adamc@194:   fun R cases b => if b
adamc@216:     then (hhd cases) tt INil
adamc@216:     else (hhd (htl cases)) tt INil.
adamc@194: Eval compute in size bool_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun b : bool => if b then 1 else 1
adamc@219:      : bool -> nat
adam@302: ]]
adam@302: *)
adamc@194: 
adamc@194: Definition nat_fix : fixDenote nat nat_dt :=
adamc@194:   fun R cases => fix F (n : nat) : R :=
adamc@194:     match n with
adamc@216:       | O => (hhd cases) tt INil
adamc@216:       | S n' => (hhd (htl cases)) tt (ICons (F n') INil)
adamc@194:     end.
adamc@219: 
adamc@219: (** To peek at the [size] function for [nat], it is useful to avoid full computation, so that the recursive definition of addition is not expanded inline.  We can accomplish this with proper flags for the [cbv] reduction strategy. *)
adamc@219: 
adamc@194: Eval cbv beta iota delta -[plus] in size nat_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fix F (n : nat) : nat := match n with
adamc@219:                                 | 0 => 1
adamc@219:                                 | S n' => F n' + 1
adamc@219:                                 end
adamc@219:      : nat -> nat
adam@302: ]]
adam@302: *)
adamc@194: 
adamc@194: Definition list_fix (A : Type) : fixDenote (list A) (list_dt A) :=
adamc@194:   fun R cases => fix F (ls : list A) : R :=
adamc@194:     match ls with
adamc@216:       | nil => (hhd cases) tt INil
adamc@216:       | x :: ls' => (hhd (htl cases)) x (ICons (F ls') INil)
adamc@194:     end.
adamc@194: Eval cbv beta iota delta -[plus] in fun A => size (@list_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun A : Type =>
adamc@219:        fix F (ls : list A) : nat :=
adamc@219:          match ls with
adamc@219:          | nil => 1
adamc@219:          | _ :: ls' => F ls' + 1
adamc@219:          end
adamc@219:      : forall A : Type, list A -> nat
adam@302: ]]
adam@302: *)
adamc@194: 
adamc@194: Definition tree_fix (A : Type) : fixDenote (tree A) (tree_dt A) :=
adamc@194:   fun R cases => fix F (t : tree A) : R :=
adamc@194:     match t with
adamc@216:       | Leaf x => (hhd cases) x INil
adamc@216:       | Node t1 t2 => (hhd (htl cases)) tt (ICons (F t1) (ICons (F t2) INil))
adamc@194:     end.
adamc@194: Eval cbv beta iota delta -[plus] in fun A => size (@tree_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun A : Type =>
adamc@219:        fix F (t : tree A) : nat :=
adamc@219:          match t with
adamc@219:          | Leaf _ => 1
adamc@219:          | Node t1 t2 => F t1 + (F t2 + 1)
adamc@219:          end
adamc@219:      : forall A : Type, tree A -> n
adam@302: ]]
adam@302: *)
adamc@198: (* end thide *)
adamc@195: 
adamc@195: 
adamc@195: (** ** Pretty-Printing *)
adamc@195: 
adamc@198: (* EX: Define a generic pretty-printing function. *)
adamc@198: 
adamc@219: (** It is also useful to do generic pretty-printing of datatype values, rendering them as human-readable strings.  To do so, we will need a bit of metadata for each constructor.  Specifically, we need the name to print for the constructor and the function to use to render its non-recursive arguments.  Everything else can be done generically. *)
adamc@219: 
adamc@198: (* begin thide *)
adamc@195: Record print_constructor (c : constructor) : Type := PI {
adamc@195:   printName : string;
adamc@195:   printNonrec : nonrecursive c -> string
adamc@195: }.
adamc@195: 
adamc@219: (** It is useful to define a shorthand for applying the constructor [PI].  By applying it explicitly to an unknown application of the constructor [Con], we help type inference work. *)
adamc@219: 
adamc@195: Notation "^" := (PI (Con _ _)).
adamc@195: 
adamc@219: (** As in earlier examples, we define the type of metadata for a datatype to be a heterogeneous list type collecting metadata for each constructor. *)
adamc@219: 
adamc@195: Definition print_datatype := hlist print_constructor.
adamc@195: 
adamc@219: (** We will be doing some string manipulation here, so we import the notations associated with strings. *)
adamc@219: 
adamc@219: Local Open Scope string_scope.
adamc@219: 
adamc@219: (** Now it is easy to implement our generic printer, using another function from [DepList.] *)
adamc@219: 
adamc@219: Check hmap.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:   hmap
adamc@219:      : forall (A : Type) (B1 B2 : A -> Type),
adamc@219:        (forall x : A, B1 x -> B2 x) ->
adamc@219:        forall ls : list A, hlist B1 ls -> hlist B2 ls
adam@302: ]]
adam@302: *)
adamc@195: 
adamc@195: Definition print T dt (pr : print_datatype dt) (fx : fixDenote T dt) : T -> string :=
adamc@195:   fx string (hmap (B1 := print_constructor) (B2 := constructorDenote string)
adamc@195:     (fun _ pc x r => printName pc ++ "(" ++ printNonrec pc x
adamc@195:       ++ foldr (fun s acc => ", " ++ s ++ acc) ")" r) pr).
adamc@198: (* end thide *)
adamc@195: 
adamc@219: (** Some simple tests establish that [print] gets the job done. *)
adamc@219: 
adamc@216: Eval compute in print HNil Empty_set_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun emp : Empty_set => match emp return string with
adamc@219:                               end
adamc@219:      : Empty_set -> string
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@216: Eval compute in print (^ "tt" (fun _ => "") ::: HNil) unit_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun _ : unit => "tt()"
adamc@219:      : unit -> string
adam@302:    ]]
adam@302:    *)
adamc@219: 
adamc@195: Eval compute in print (^ "true" (fun _ => "")
adamc@195:   ::: ^ "false" (fun _ => "")
adamc@216:   ::: HNil) bool_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:    = fun b : bool => if b then "true()" else "false()"
adamc@219:    : bool -> s
adam@302:    ]]
adam@302:    *)
adamc@195: 
adamc@195: Definition print_nat := print (^ "O" (fun _ => "")
adamc@195:   ::: ^ "S" (fun _ => "")
adamc@216:   ::: HNil) nat_fix.
adamc@195: Eval cbv beta iota delta -[append] in print_nat.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fix F (n : nat) : string :=
adamc@219:          match n with
adamc@219:          | 0%nat => "O" ++ "(" ++ "" ++ ")"
adamc@219:          | S n' => "S" ++ "(" ++ "" ++ ", " ++ F n' ++ ")"
adamc@219:          end
adamc@219:      : nat -> string
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@195: Eval simpl in print_nat 0.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = "O()"
adamc@219:      : string
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@195: Eval simpl in print_nat 1.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = "S(, O())"
adamc@219:      : string
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@195: Eval simpl in print_nat 2.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = "S(, S(, O()))"
adamc@219:      : string
adam@302:      ]]
adam@302:      *)
adamc@195: 
adamc@195: Eval cbv beta iota delta -[append] in fun A (pr : A -> string) =>
adamc@195:   print (^ "nil" (fun _ => "")
adamc@195:   ::: ^ "cons" pr
adamc@216:   ::: HNil) (@list_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (A : Type) (pr : A -> string) =>
adamc@219:        fix F (ls : list A) : string :=
adamc@219:          match ls with
adamc@219:          | nil => "nil" ++ "(" ++ "" ++ ")"
adamc@219:          | x :: ls' => "cons" ++ "(" ++ pr x ++ ", " ++ F ls' ++ ")"
adamc@219:          end
adamc@219:      : forall A : Type, (A -> string) -> list A -> string
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@195: Eval cbv beta iota delta -[append] in fun A (pr : A -> string) =>
adamc@195:   print (^ "Leaf" pr
adamc@195:   ::: ^ "Node" (fun _ => "")
adamc@216:   ::: HNil) (@tree_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (A : Type) (pr : A -> string) =>
adamc@219:        fix F (t : tree A) : string :=
adamc@219:          match t with
adamc@219:          | Leaf x => "Leaf" ++ "(" ++ pr x ++ ")"
adamc@219:          | Node t1 t2 =>
adamc@219:              "Node" ++ "(" ++ "" ++ ", " ++ F t1 ++ ", " ++ F t2 ++ ")"
adamc@219:          end
adamc@219:      : forall A : Type, (A -> string) -> tree A -> string
adam@302:      ]]
adam@302:      *)
adamc@196: 
adam@358: (** Some of these simplified terms seem overly complex because we have turned off simplification of calls to [append], which is what uses of the [++] operator desugar to.  Selective [++] simplification would combine adjacent string literals, yielding more or less the code we would write manually to implement this printing scheme. *)
adam@358: 
adamc@196: 
adamc@196: (** ** Mapping *)
adamc@196: 
adamc@198: (* EX: Define a generic [map] function. *)
adamc@198: 
adamc@219: (** By this point, we have developed enough machinery that it is old hat to define a generic function similar to the list [map] function. *)
adamc@219: 
adamc@198: (* begin thide *)
adamc@219: Definition map T dt (dd : datatypeDenote T dt) (fx : fixDenote T dt) (f : T -> T)
adamc@219:   : T -> T :=
adamc@196:   fx T (hmap (B1 := constructorDenote T) (B2 := constructorDenote T)
adamc@196:     (fun _ c x r => f (c x r)) dd).
adamc@198: (* end thide *)
adamc@196: 
adamc@196: Eval compute in map Empty_set_den Empty_set_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (_ : Empty_set -> Empty_set) (emp : Empty_set) =>
adamc@219:        match emp return Empty_set with
adamc@219:        end
adamc@219:      : (Empty_set -> Empty_set) -> Empty_set -> Empty_set
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval compute in map unit_den unit_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (f : unit -> unit) (_ : unit) => f tt
adamc@219:      : (unit -> unit) -> unit -> unit
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval compute in map bool_den bool_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (f : bool -> bool) (b : bool) => if b then f true else f false
adamc@219:      : (bool -> bool) -> bool -> bool
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval compute in map nat_den nat_fix.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun f : nat -> nat =>
adamc@219:        fix F (n : nat) : nat :=
adamc@219:          match n with
adamc@219:          | 0%nat => f 0%nat
adamc@219:          | S n' => f (S (F n'))
adamc@219:          end
adamc@219:      : (nat -> nat) -> nat -> nat
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval compute in fun A => map (list_den A) (@list_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (A : Type) (f : list A -> list A) =>
adamc@219:        fix F (ls : list A) : list A :=
adamc@219:          match ls with
adamc@219:          | nil => f nil
adamc@219:          | x :: ls' => f (x :: F ls')
adamc@219:          end
adamc@219:      : forall A : Type, (list A -> list A) -> list A -> list A
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval compute in fun A => map (tree_den A) (@tree_fix A).
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = fun (A : Type) (f : tree A -> tree A) =>
adamc@219:        fix F (t : tree A) : tree A :=
adamc@219:          match t with
adamc@219:          | Leaf x => f (Leaf x)
adamc@219:          | Node t1 t2 => f (Node (F t1) (F t2))
adamc@219:          end
adamc@219:      : forall A : Type, (tree A -> tree A) -> tree A -> tree A
adam@302:      ]]
adam@302:      *)
adamc@196: 
adam@358: (** These [map] functions are just as easy to use as those we write by hand.  Can you figure out the input-output pattern that [map_nat S] displays in these examples? *)
adam@358: 
adamc@196: Definition map_nat := map nat_den nat_fix.
adamc@196: Eval simpl in map_nat S 0.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = 1%nat
adamc@219:      : nat
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval simpl in map_nat S 1.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = 3%nat
adamc@219:      : nat
adam@302:      ]]
adam@302:      *)
adamc@219: 
adamc@196: Eval simpl in map_nat S 2.
adamc@219: (** %\vspace{-.15in}% [[
adamc@219:      = 5%nat
adamc@219:      : nat
adam@302:      ]]
adam@302:      *)
adamc@196: 
adam@358: (** We get [map_nat S n] = [2 * n + 1], because the mapping process adds an extra [S] at every level of the inductive tree that defines a natural, including at the last level, the [O] constructor. *)
adam@358: 
adamc@196: 
adamc@196: (** * Proving Theorems about Recursive Definitions *)
adamc@196: 
adamc@219: (** We would like to be able to prove theorems about our generic functions.  To do so, we need to establish additional well-formedness properties that must hold of pieces of evidence. *)
adamc@219: 
adamc@198: (* begin thide *)
adamc@196: Section ok.
adamc@196:   Variable T : Type.
adamc@196:   Variable dt : datatype.
adamc@196: 
adamc@196:   Variable dd : datatypeDenote T dt.
adamc@196:   Variable fx : fixDenote T dt.
adamc@196: 
adamc@219:   (** First, we characterize when a piece of evidence about a datatype is acceptable.  The basic idea is that the type [T] should really be an inductive type with the definition given by [dd].  Semantically, inductive types are characterized by the ability to do induction on them.  Therefore, we require that the usual induction principle is true, with respect to the constructors given in the encoding [dd]. *)
adamc@219: 
adamc@196:   Definition datatypeDenoteOk :=
adamc@196:     forall P : T -> Prop,
adamc@196:       (forall c (m : member c dt) (x : nonrecursive c) (r : ilist T (recursive c)),
adamc@215:         (forall i : fin (recursive c), P (get r i))
adamc@196:         -> P ((hget dd m) x r))
adamc@196:       -> forall v, P v.
adamc@196: 
adam@358:   (** This definition can take a while to digest.  The quantifier over [m : member c dt] is considering each constructor in turn; like in normal induction principles, each constructor has an associated proof case.  The expression [hget dd m] then names the constructor we have selected.  After binding [m], we quantify over all possible arguments (encoded with [x] and [r]) to the constructor that [m] selects.  Within each specific case, we quantify further over [i : fin (][recursive c)] to consider all of our induction hypotheses, one for each recursive argument of the current constructor.
adamc@219: 
adamc@219:      We have completed half the burden of defining side conditions.  The other half comes in characterizing when a recursion scheme [fx] is valid.  The natural condition is that [fx] behaves appropriately when applied to any constructor application. *)
adamc@219: 
adamc@196:   Definition fixDenoteOk :=
adamc@196:     forall (R : Type) (cases : datatypeDenote R dt)
adamc@196:       c (m : member c dt)
adamc@196:       (x : nonrecursive c) (r : ilist T (recursive c)),
adamc@216:       fx cases ((hget dd m) x r)
adamc@216:       = (hget cases m) x (imap (fx cases) r).
adamc@219: 
adamc@219:   (** As for [datatypeDenoteOk], we consider all constructors and all possible arguments to them by quantifying over [m], [x], and [r].  The lefthand side of the equality that follows shows a call to the recursive function on the specific constructor application that we selected.  The righthand side shows an application of the function case associated with constructor [m], applied to the non-recursive arguments and to appropriate recursive calls on the recursive arguments. *)
adamc@219: 
adamc@196: End ok.
adamc@196: 
adamc@219: (** We are now ready to prove that the [size] function we defined earlier always returns positive results.  First, we establish a simple lemma. *)
adamc@196: 
adamc@196: Lemma foldr_plus : forall n (ils : ilist nat n),
adamc@196:   foldr plus 1 ils > 0.
adamc@216:   induction ils; crush.
adamc@196: Qed.
adamc@198: (* end thide *)
adamc@196: 
adamc@197: Theorem size_positive : forall T dt
adamc@197:   (dd : datatypeDenote T dt) (fx : fixDenote T dt)
adamc@197:   (dok : datatypeDenoteOk dd) (fok : fixDenoteOk dd fx)
adamc@196:   (v : T),
adamc@196:   size fx v > 0.
adamc@198: (* begin thide *)
adamc@219:   unfold size; intros.
adamc@219:   (** [[
adamc@219:   ============================
adamc@219:    fx nat
adamc@219:      (hmake
adamc@219:         (fun (x : constructor) (_ : nonrecursive x)
adamc@219:            (r : ilist nat (recursive x)) => foldr plus 1%nat r) dt) v > 0
adamc@219:     ]]
adamc@219:       
adamc@219:     Our goal is an inequality over a particular call to [size], with its definition expanded.  How can we proceed here?  We cannot use [induction] directly, because there is no way for Coq to know that [T] is an inductive type.  Instead, we need to use the induction principle encoded in our hypothesis [dok] of type [datatypeDenoteOk dd].  Let us try applying it directly.
adamc@219:     [[
adamc@219:   apply dok.
adam@358:     ]]
adam@358: %\vspace{-.3in}%
adam@358: <<
adamc@219: Error: Impossible to unify "datatypeDenoteOk dd" with
adamc@219:  "fx nat
adamc@219:     (hmake
adamc@219:        (fun (x : constructor) (_ : nonrecursive x)
adamc@219:           (r : ilist nat (recursive x)) => foldr plus 1%nat r) dt) v > 0".
adam@358: >>
adamc@219: 
adamc@219:     Matching the type of [dok] with the type of our conclusion requires more than simple first-order unification, so [apply] is not up to the challenge.  We can use the [pattern] tactic to get our goal into a form that makes it apparent exactly what the induction hypothesis is. *)
adamc@219: 
adamc@219:   pattern v.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   ============================
adamc@219:    (fun t : T =>
adamc@219:     fx nat
adamc@219:       (hmake
adamc@219:          (fun (x : constructor) (_ : nonrecursive x)
adamc@219:             (r : ilist nat (recursive x)) => foldr plus 1%nat r) dt) t > 0) v
adam@302:       ]]
adam@302:       *)
adamc@219: 
adamc@219:   apply dok; crush.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   H : forall i : fin (recursive c),
adamc@219:       fx nat
adamc@219:         (hmake
adamc@219:            (fun (x : constructor) (_ : nonrecursive x)
adamc@219:               (r : ilist nat (recursive x)) => foldr plus 1%nat r) dt)
adamc@219:         (get r i) > 0
adamc@219:   ============================
adamc@219:    hget
adamc@219:      (hmake
adamc@219:         (fun (x0 : constructor) (_ : nonrecursive x0)
adamc@219:            (r0 : ilist nat (recursive x0)) => foldr plus 1%nat r0) dt) m x
adamc@219:      (imap
adamc@219:         (fx nat
adamc@219:            (hmake
adamc@219:               (fun (x0 : constructor) (_ : nonrecursive x0)
adamc@219:                  (r0 : ilist nat (recursive x0)) => 
adamc@219:                foldr plus 1%nat r0) dt)) r) > 0
adamc@219:     ]]
adamc@219: 
adamc@219:     An induction hypothesis [H] is generated, but we turn out not to need it for this example.  We can simplify the goal using a library theorem about the composition of [hget] and [hmake]. *)
adamc@219: 
adamc@219:   rewrite hget_hmake.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   ============================
adamc@219:    foldr plus 1%nat
adamc@219:      (imap
adamc@219:         (fx nat
adamc@219:            (hmake
adamc@219:               (fun (x0 : constructor) (_ : nonrecursive x0)
adamc@219:                  (r0 : ilist nat (recursive x0)) => 
adamc@219:                foldr plus 1%nat r0) dt)) r) > 0
adamc@219:     ]]
adamc@219: 
adamc@219:     The lemma we proved earlier finishes the proof. *)
adamc@219: 
adamc@219:   apply foldr_plus.
adamc@219: 
adamc@219:   (** Using hints, we can redo this proof in a nice automated form. *)
adamc@219: 
adamc@219:   Restart.
adamc@219: 
adamc@196:   Hint Rewrite hget_hmake : cpdt.
adamc@196:   Hint Resolve foldr_plus.
adamc@196:  
adamc@197:   unfold size; intros; pattern v; apply dok; crush.
adamc@196: Qed.
adamc@198: (* end thide *)
adamc@197: 
adamc@219: (** It turned out that, in this example, we only needed to use induction degenerately as case analysis.  A more involved theorem may only be proved using induction hypotheses.  We will give its proof only in unautomated form and leave effective automation as an exercise for the motivated reader.
adamc@219: 
adamc@219:    In particular, it ought to be the case that generic [map] applied to an identity function is itself an identity function. *)
adamc@219: 
adamc@197: Theorem map_id : forall T dt
adamc@197:   (dd : datatypeDenote T dt) (fx : fixDenote T dt)
adamc@197:   (dok : datatypeDenoteOk dd) (fok : fixDenoteOk dd fx)
adamc@197:   (v : T),
adamc@197:   map dd fx (fun x => x) v = v.
adamc@198: (* begin thide *)
adamc@219:   (** Let us begin as we did in the last theorem, after adding another useful library equality as a hint. *)
adamc@219: 
adamc@197:   Hint Rewrite hget_hmap : cpdt.
adamc@197: 
adamc@197:   unfold map; intros; pattern v; apply dok; crush.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   H : forall i : fin (recursive c),
adamc@219:       fx T
adamc@219:         (hmap
adamc@219:            (fun (x : constructor) (c : constructorDenote T x)
adamc@219:               (x0 : nonrecursive x) (r : ilist T (recursive x)) => 
adamc@219:             c x0 r) dd) (get r i) = get r i
adamc@219:   ============================
adamc@219:    hget dd m x
adamc@219:      (imap
adamc@219:         (fx T
adamc@219:            (hmap
adamc@219:               (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:                  (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) =>
adamc@219:                c0 x1 r0) dd)) r) = hget dd m x r
adamc@219:     ]]
adamc@197: 
adamc@219:     Our goal is an equality whose two sides begin with the same function call and initial arguments.  We believe that the remaining arguments are in fact equal as well, and the [f_equal] tactic applies this reasoning step for us formally. *)
adamc@219: 
adamc@197:   f_equal.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   ============================
adamc@219:    imap
adamc@219:      (fx T
adamc@219:         (hmap
adamc@219:            (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:               (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) =>
adamc@219:             c0 x1 r0) dd)) r = r
adamc@219:     ]]
adamc@219: 
adamc@219:     At this point, it is helpful to proceed by an inner induction on the heterogeneous list [r] of recursive call results.  We could arrive at a cleaner proof by breaking this step out into an explicit lemma, but here we will do the induction inline to save space.*)
adamc@219: 
adamc@219:   induction r; crush.
adamc@219: 
adamc@219:   (** The base case is discharged automatically, and the inductive case looks like this, where [H] is the outer IH (for induction over [T] values) and [IHn] is the inner IH (for induction over the recursive arguments).
adamc@219:      [[
adamc@219:   H : forall i : fin (S n),
adamc@219:       fx T
adamc@219:         (hmap
adamc@219:            (fun (x : constructor) (c : constructorDenote T x)
adamc@219:               (x0 : nonrecursive x) (r : ilist T (recursive x)) => 
adamc@219:             c x0 r) dd)
adamc@219:         (match i in (fin n') return ((fin (pred n') -> T) -> T) with
adamc@219:          | First n => fun _ : fin n -> T => a
adamc@219:          | Next n idx' => fun get_ls' : fin n -> T => get_ls' idx'
adamc@219:          end (get r)) =
adamc@219:       match i in (fin n') return ((fin (pred n') -> T) -> T) with
adamc@219:       | First n => fun _ : fin n -> T => a
adamc@219:       | Next n idx' => fun get_ls' : fin n -> T => get_ls' idx'
adamc@219:       end (get r)
adamc@219:   IHr : (forall i : fin n,
adamc@219:          fx T
adamc@219:            (hmap
adamc@219:               (fun (x : constructor) (c : constructorDenote T x)
adamc@219:                  (x0 : nonrecursive x) (r : ilist T (recursive x)) => 
adamc@219:                c x0 r) dd) (get r i) = get r i) ->
adamc@219:         imap
adamc@219:           (fx T
adamc@219:              (hmap
adamc@219:                 (fun (x : constructor) (c : constructorDenote T x)
adamc@219:                    (x0 : nonrecursive x) (r : ilist T (recursive x)) =>
adamc@219:                  c x0 r) dd)) r = r
adamc@219:   ============================
adamc@219:    ICons
adamc@219:      (fx T
adamc@219:         (hmap
adamc@219:            (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:               (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) =>
adamc@219:             c0 x1 r0) dd) a)
adamc@219:      (imap
adamc@219:         (fx T
adamc@219:            (hmap
adamc@219:               (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:                  (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) =>
adamc@219:                c0 x1 r0) dd)) r) = ICons a r
adamc@219:     ]]
adamc@219: 
adamc@219:     We see another opportunity to apply [f_equal], this time to split our goal into two different equalities over corresponding arguments.  After that, the form of the first goal matches our outer induction hypothesis [H], when we give type inference some help by specifying the right quantifier instantiation. *)
adamc@219: 
adamc@219:   f_equal.
adamc@219:   apply (H First).
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   ============================
adamc@219:    imap
adamc@219:      (fx T
adamc@219:         (hmap
adamc@219:            (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:               (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) => 
adamc@219:             c0 x1 r0) dd)) r = r
adamc@219:     ]]
adamc@219: 
adamc@219:     Now the goal matches the inner IH [IHr]. *)
adamc@219: 
adamc@219:   apply IHr; crush.
adam@358:   (** %\vspace{-.15in}%[[
adamc@219:   i : fin n
adamc@219:   ============================
adamc@219:    fx T
adamc@219:      (hmap
adamc@219:         (fun (x0 : constructor) (c0 : constructorDenote T x0)
adamc@219:            (x1 : nonrecursive x0) (r0 : ilist T (recursive x0)) => 
adamc@219:          c0 x1 r0) dd) (get r i) = get r i
adamc@219:     ]]
adamc@219: 
adamc@219:     We can finish the proof by applying the outer IH again, specialized to a different [fin] value. *)
adamc@219: 
adamc@216:   apply (H (Next i)).
adamc@197: Qed.
adamc@198: (* end thide *)
adam@358: 
adam@358: (** The proof involves complex subgoals, but, still, few steps are required, and then we may reuse our work across a variety of datatypes. *)