HoTT/HoTT — pull request #359 by JasonGross (2014-04-03 03:32:25+00:00)
Title: Unified functorialized yoneda lemma

Alas, I still don't really understand the Yoneda lemma.

This requires _a lot_ of funext munging. The rule that I've used is one
instance of Funext for every occurrence that appears in the type,
together with one extra one that downward_closed instances of are used
for, e.g., [path_forall] in the middle of the proof. Perhaps @mattam82
can suggest a way to not need so many instances of [Funext].

Also, the proof is very long. I'd be happy if anyone could clean it up.

It's also unfortunately rather slow. I suspect some combination of
proof size, typeclass resolution, and maybe universe constraint
checking, but I'm not entirely sure. Help speeding things up would also
make me happy.

```
After | File Name | Before
-------------------------------------------------------------------------------
10m58.40s | Total | 8m42.36s
-------------------------------------------------------------------------------
2m23.81s | categories/Comma/ProjectionFunctors | 1m44.49s
0m55.14s | categories/Yoneda | 0m08.05s
0m34.69s | categories/Adjoint/Composition/AssociativityLaw | 0m33.46s
0m27.57s | categories/Grothendieck/PseudofunctorToCat | 0m24.60s
0m26.48s | categories/ExponentialLaws/Law4/Functors | 0m16.69s
0m21.61s | categories/Comma/InducedFunctors | 0m15.64s
0m18.55s | categories/FunctorCategory/Dual | 0m17.77s
0m17.40s | categories/Adjoint/UnitCounitCoercions | 0m17.55s
0m15.39s | categories/Functor/Pointwise/Properties | 0m12.90s
0m14.97s | categories/Pseudofunctor/Core | 0m12.94s
0m12.98s | categories/Adjoint/Composition/Core | 0m12.56s
0m12.70s | hit/Flattening | 0m12.66s
0m12.32s | categories/Adjoint/Dual | 0m11.88s
0m11.54s | categories/Adjoint/Composition/IdentityLaws | 0m10.56s
0m11.27s | categories/Pseudofunctor/FromFunctor | 0m11.11s
0m09.87s | categories/ExponentialLaws/Law2/Functors | 0m05.56s
0m09.82s | categories/ExponentialLaws/Law1/Law | 0m09.36s
0m07.85s | categories/Functor/Prod/Universal | 0m08.25s
0m07.81s | categories/GroupoidCategory/Morphisms | 0m08.18s
0m07.15s | categories/UniversalProperties | 0m07.28s
0m07.11s | hit/Connectedness | 0m06.82s
0m06.78s | categories/Functor/Prod/Functorial | 0m02.97s
0m06.78s | categories/Comma/Dual | 0m07.54s
0m06.59s | categories/Adjoint/Paths | 0m06.78s
0m06.44s | categories/Adjoint/UnitCounit | 0m06.37s
0m06.31s | categories/Structure/IdentityPrinciple | 0m06.70s
0m05.75s | categories/Functor/Sum | 0m05.54s
0m05.66s | categories/Functor/Paths | 0m06.11s
0m05.59s | categories/Category/Morphisms | 0m05.65s
0m05.04s | EquivalenceVarieties | 0m05.00s
0m04.96s | categories/DualFunctor | 0m05.27s
0m04.55s | categories/Category/Sigma/OnMorphisms | 0m04.37s
0m04.09s | categories/Functor/Attributes | 0m02.24s
0m03.64s | categories/ProductLaws | 0m03.60s
0m03.49s | types/ObjectClassifier | 0m03.44s
0m03.43s | categories/Structure/Core | 0m03.63s
0m03.30s | categories/Functor/Composition/Functorial | 0m00.97s
0m03.08s | types/Sigma | 0m02.94s
0m03.05s | categories/FunctorCategory/Functorial | 0m02.62s
0m02.98s | categories/Adjoint/UniversalMorphisms | 0m02.69s
0m02.79s | categories/Limits/Core | 0m01.17s
0m02.71s | categories/Grothendieck/ToSet | 0m02.50s
0m02.67s | categories/NaturalTransformation/Pointwise | 0m01.33s
0m02.58s | categories/NaturalTransformation/Isomorphisms | 0m01.91s
0m02.53s | Equivalences | 0m02.58s
0m02.22s | categories/Category/Sum | 0m02.30s
0m02.21s | categories/FunctorCategory/Morphisms | 0m01.70s
0m02.10s | categories/Category/Sigma/Core | 0m02.08s
0m02.05s | categories/Comma/Core | 0m02.18s
0m01.94s | PathGroupoids | 0m01.91s
0m01.88s | categories/ExponentialLaws/Law N/A | 0m01.03s
0m01.86s | categories/NaturalTransformation/Dual | 0m01.86s
0m01.71s | categories/HomFunctor | 0m01.78s
0m01.68s | categories/Functor/Pointwise | 0m01.05s
0m01.66s | contrib/HoTTBook | 0m00.66s
0m01.64s | categories/NaturalTransformation/Paths | 0m01.58s
0m01.45s | categories/ExponentialLaws/Law1/Functors | 0m00.97s
0m01.32s | categories/Category/Prod | 0m01.30s
0m01.31s | categories/NaturalTransformation/Composition/Laws | 0m01.31s
0m01.30s | types/Prod | 0m01.30s
0m01.28s | categories/Category/Sigma/OnObjects | 0m01.26s
0m01.11s | categories/categories | 0m00.55s
0m01.11s | contrib/HoTTBookExercises | 0m01.01s
0m01.01s | categories/CategoryOfSections/Core | 0m01.06s
0m00.96s | categories/NaturalTransformation/Prod | 0m00.94s
0m00.94s | hit/Spheres | 0m00.86s
0m00.88s | types/Paths | 0m00.84s
0m00.85s | hit/epi | 0m00.91s
0m00.85s | categories/Functor/Prod | 0m00.82s
0m00.84s | categories/SetCategory/Morphisms | N/A
0m00.83s | categories/Limits/Functors | 0m00.42s
0m00.81s | categories/KanExtensions/Functors | 0m00.44s
0m00.79s | Trunc | 0m00.72s
0m00.77s | categories/Functor/Identity | 0m00.84s
0m00.76s | categories/ExponentialLaws/Law3/Functors | 0m00.44s
0m00.67s | categories/InitialTerminalCategory | 0m00.66s
0m00.65s | types/Universe | 0m00.66s
0m00.65s | categories/Comma/Projection | 0m00.56s
0m00.64s | types/Sum | 0m00.63s
0m00.62s | hit/quotient | 0m00.65s
0m00.62s | categories/NaturalTransformation/Composition/Core | 0m00.71s
0m00.58s | categories/KanExtensions/Core | 0m00.27s
0m00.57s | categories/NaturalTransformation/Sum | 0m00.52s
0m00.57s | hit/Circle | 0m00.52s
0m00.56s | Functorish | 0m00.51s
0m00.53s | hit/Suspension | 0m00.58s
0m00.52s | types/Record | 0m00.50s
0m00.52s | categories/Functor/Composition/Laws | 0m00.58s
0m00.48s | categories/Functor/Functor | 0m00.30s
0m00.46s | HSet | 0m00.39s
0m00.45s | Tactics | 0m00.45s
0m00.43s | HProp | 0m00.43s
0m00.43s | categories/NaturalTransformation/Composition/Functorial | 0m00.30s
0m00.42s | types/Forall | 0m00.44s
0m00.41s | categories/Cat/Core | 0m00.39s
0m00.39s | categories/NaturalTransformation/Identity | 0m00.42s
0m00.38s | categories/Cat/Morphisms | 0m00.32s
0m00.36s | categories/Functor/Dual | 0m00.38s
0m00.35s | categories/ExponentialLaws/ExponentialLaws | 0m00.26s
0m00.34s | Misc | 0m00.29s
0m00.34s | TruncType | 0m00.33s
0m00.34s | Fibrations | 0m00.35s
0m00.33s | categories/Grothendieck/Grothendieck | 0m00.26s
0m00.31s | categories/IndiscreteCategory | 0m00.30s
0m00.27s | hit/minus1Trunc | 0m00.25s
0m00.26s | categories/DependentProduct | 0m00.22s
0m00.26s | categories/Grothendieck/ToCat | 0m00.22s
0m00.26s | categories/Category/Objects | 0m00.20s
0m00.26s | types/Arrow | 0m00.27s
0m00.24s | categories/Functor/Composition/Core | 0m00.29s
0m00.24s | categories/Notations | 0m00.24s
0m00.21s | categories/Utf8 | 0m00.21s
0m00.20s | categories/Functor/Prod/Prod | 0m00.17s
0m00.20s | categories/SetCategory/Functors/Functors | 0m00.19s
0m00.20s | categories/Comma/Comma | 0m00.17s
0m00.20s | categories/Comma/Notations | 0m00.16s
0m00.20s | categories/Adjoint/Adjoint | 0m00.20s
0m00.20s | types/Bool | 0m00.21s
0m00.19s | categories/GroupoidCategory/Core | 0m00.18s
0m00.19s | FunextVarieties | 0m00.16s
0m00.19s | categories/FunctorCategory/Core | 0m00.16s
0m00.18s | categories/NaturalTransformation/NaturalTransformation | 0m00.20s
0m00.18s | hit/iso | 0m00.21s
0m00.18s | categories/FunctorCategory/FunctorCategory | 0m00.15s
0m00.18s | categories/NatCategory | 0m00.20s
0m00.18s | categories/Adjoint/Composition/Composition | 0m00.15s
0m00.18s | categories/ExponentialLaws/Law1/Law1 | 0m00.14s
0m00.18s | categories/NaturalTransformation/Utf8 | 0m00.13s
0m00.18s | categories/Adjoint/Composition/LawsTactic | 0m00.15s
0m00.17s | categories/Adjoint/Utf8 | 0m00.14s
0m00.17s | categories/Adjoint/Notations | 0m00.16s
0m00.16s | Conjugation | 0m00.19s
0m00.16s | categories/KanExtensions/KanExtensions | 0m00.16s
0m00.16s | categories/Cat/Cat | 0m00.17s
0m00.16s | categories/FunctorCategory/Utf8 | 0m00.11s
0m00.16s | HoTT | 0m00.16s
0m00.16s | categories/Category/Dual | 0m00.14s
0m00.16s | categories/Adjoint/Identity | 0m00.14s
0m00.16s | categories/Functor/Notations | 0m00.17s
0m00.16s | categories/Pseudofunctor/Pseudofunctor | 0m00.18s
0m00.16s | categories/NaturalTransformation/Notations | 0m00.21s
0m00.16s | Overture | 0m00.16s
0m00.15s | categories/Limits/Limits | 0m00.18s
0m00.15s | categories/Category/Univalent | 0m00.14s
0m00.15s | categories/Profunctor/Representable | 0m00.16s
0m00.15s | categories/ExponentialLaws/Law2/Law2 | 0m00.16s
0m00.15s | categories/FunctorCategory/Notations | 0m00.10s
0m00.14s | categories/Comma/Utf8 | 0m00.16s
0m00.14s | Contractible | 0m00.12s
0m00.14s | hit/Interval | 0m00.14s
0m00.14s | categories/Functor/Composition/Composition | 0m00.12s
0m00.14s | categories/Profunctor/Notations | 0m00.10s
0m00.14s | categories/ExponentialLaws/Law4/Law4 | 0m00.09s
0m00.14s | categories/NaturalTransformation/Core | 0m00.16s
0m00.14s | categories/Category/Core | 0m00.15s
0m00.14s | hit/TwoSphere | 0m00.15s
0m00.14s | categories/NaturalTransformation/Composition/Composition | 0m00.10s
0m00.14s | categories/Functor/Pointwise/Pointwise | 0m00.10s
0m00.14s | categories/Profunctor/Utf8 | 0m00.10s
0m00.13s | categories/Category/Utf8 | 0m00.12s
0m00.13s | categories/SetCategory/Core | 0m00.12s
0m00.12s | categories/ExponentialLaws/Law3/Law3 | 0m00.16s
0m00.12s | categories/DiscreteCategory | 0m00.10s
0m00.12s | categories/Adjoint/Core | 0m00.11s
0m00.12s | categories/Structure/Structure | 0m00.12s
0m00.12s | hit/unique_choice | 0m00.14s
0m00.12s | categories/Category/Category | 0m00.16s
0m00.12s | categories/Functor/Utf8 | 0m00.17s
0m00.12s | categories/Category/Subcategory/Subcategory | 0m00.12s
0m00.12s | categories/Profunctor/Identity | 0m00.14s
0m00.12s | types/Unit | 0m00.13s
0m00.12s | categories/Category/Sigma/Sigma | 0m00.11s
0m00.12s | categories/Category/Subcategory/Full | 0m00.12s
0m00.12s | categories/CategoryOfSections/CategoryOfSections | 0m00.09s
0m00.11s | categories/GroupoidCategory/GroupoidCategory | 0m00.10s
0m00.11s | categories/Profunctor/Core | 0m00.10s
0m00.11s | coq/Init/Peano | 0m00.12s
0m00.11s | categories/Profunctor/Profunctor | 0m00.11s
0m00.11s | categories/Category/Subcategory/Wide | 0m00.12s
0m00.10s | categories/Functor/Core | 0m00.10s
0m00.10s | Pointed | 0m00.08s
0m00.10s | categories/SetCategory/SetCategory | 0m00.12s
0m00.10s | UnivalenceAxiom | 0m00.08s
0m00.10s | categories/Structure/Utf8 | 0m00.08s
0m00.10s | hit/Truncations | 0m00.14s
0m00.09s | types/UniverseLevel | 0m00.07s
0m00.09s | categories/Category/Notations | 0m00.11s
0m00.08s | coq/Init/Specif | 0m00.07s
0m00.08s | categories/Structure/Notations | 0m00.09s
0m00.08s | coq/Init/Logic_Type | 0m00.05s
0m00.08s | types/Empty | 0m00.06s
0m00.06s | coq/Init/Datatypes | 0m00.05s
0m00.06s | categories/Category/Strict | 0m00.06s
0m00.05s | FunextAxiom | 0m00.06s
0m00.04s | coq/Init/Prelude | 0m00.04s
0m00.04s | coq/Program/Tactics | 0m00.06s
0m00.03s | coq/Bool/Bool | 0m00.03s
0m00.02s | coq/Init/Notations | 0m00.03s
0m00.02s | coq/Init/Logic | 0m00.03s
0m00.02s | coq/Init/Tactics | 0m00.03s
```