Mercurial > cpdt > repo
diff src/MoreDep.v @ 370:549d604c3d16
Move exercises out of mainline book
author | Adam Chlipala <adam@chlipala.net> |
---|---|
date | Fri, 02 Mar 2012 09:58:00 -0500 |
parents | b809d3a8a5b1 |
children | f7c2bf7f1324 |
line wrap: on
line diff
--- a/src/MoreDep.v Fri Dec 16 13:28:11 2011 -0500 +++ b/src/MoreDep.v Fri Mar 02 09:58:00 2012 -0500 @@ -1216,20 +1216,3 @@ Eval simpl in matches a_star "aa". (** Evaluation inside Coq does not scale very well, so it is easy to build other tests that run for hours or more. Such cases are better suited to execution with the extracted OCaml code. *) - - -(** * Exercises *) - -(** %\begin{enumerate}%#<ol># - -%\item%#<li># Define a kind of dependently typed lists, where a list's type index gives a lower bound on how many of its elements satisfy a particular predicate. In particular, for an arbitrary set [A] and a predicate [P] over it: -%\begin{enumerate}%#<ol># - %\item%#<li># Define a type [plist : nat -> Set]. Each [plist n] should be a list of [A]s, where it is guaranteed that at least [n] distinct elements satisfy [P]. There is wide latitude in choosing how to encode this. You should try to avoid using subset types or any other mechanism based on annotating non-dependent types with propositions after-the-fact.#</li># - %\item%#<li># Define a version of list concatenation that works on [plist]s. The type of this new function should express as much information as possible about the output [plist].#</li># - %\item%#<li># Define a function [plistOut] for translating [plist]s to normal [list]s.#</li># - %\item%#<li># Define a function [plistIn] for translating [list]s to [plist]s. The type of [plistIn] should make it clear that the best bound on [P]-matching elements is chosen. You may assume that you are given a dependently typed function for deciding instances of [P].#</li># - %\item%#<li># Prove that, for any list [ls], [plistOut (plistIn ls) = ls]. This should be the only part of the exercise where you use tactic-based proving.#</li># - %\item%#<li># Define a function [grab : forall n (ls : plist (][S n)), sig P]. That is, when given a [plist] guaranteed to contain at least one element satisfying [P], [grab] produces such an element. The type family [sig] is the one we met earlier for sigma types (i.e., dependent pairs of programs and proofs), and [sig P] is extensionally equivalent to [{][x : A | P x}], though the latter form uses an eta-expansion of [P] instead of [P] itself as the predicate.#</li># -#</ol>#%\end{enumerate}% #</li># - -#</ol>#%\end{enumerate}% *)