https://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&feed=atom&action=historyEs/Teoría de Categorías y Programación Funcional @ Stanford: Clase 1 - Revision history2024-03-19T02:27:20ZRevision history for this page on the wikiMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&diff=41432&oldid=prevCarlochess at 14:25, 4 August 20112011-08-04T14:25:59Z<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:25, 4 August 2011</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 59:</td>
<td colspan="2" class="diff-lineno">Line 59:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>fuente \to destino</math></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><math>fuente \to destino</math></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Given</del> <del class="diffchange diffchange-inline">a</del> <del class="diffchange diffchange-inline">graph</del> <math>G</math>, <del class="diffchange diffchange-inline">we</del> <del class="diffchange diffchange-inline">denote</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">collection</del> <del class="diffchange diffchange-inline">of</del> <del class="diffchange diffchange-inline">nodes by</del> <math><del class="diffchange diffchange-inline">G_0</del></math> <del class="diffchange diffchange-inline">and</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">collection</del> <del class="diffchange diffchange-inline">of</del> <del class="diffchange diffchange-inline">arrows</del> <del class="diffchange diffchange-inline">by</del> <math>G_1</math>. <del class="diffchange diffchange-inline">These</del> <del class="diffchange diffchange-inline">two</del> <del class="diffchange diffchange-inline">collections</del> <del class="diffchange diffchange-inline">are</del> <del class="diffchange diffchange-inline">connected</del>, <del class="diffchange diffchange-inline">and</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">graph</del> <del class="diffchange diffchange-inline">given</del> <del class="diffchange diffchange-inline">its</del> <del class="diffchange diffchange-inline">structure</del>, <del class="diffchange diffchange-inline">by</del> <del class="diffchange diffchange-inline">two</del> <del class="diffchange diffchange-inline">functions</del>: <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">source</del> <del class="diffchange diffchange-inline">function</del> <math>s:G_1\to G_0</math> <del class="diffchange diffchange-inline">and</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">target</del> <del class="diffchange diffchange-inline">function</del> <math>t:G_1\to G_0</math>.</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Dado</ins> <ins class="diffchange diffchange-inline">un</ins> <ins class="diffchange diffchange-inline">grafo</ins> <math><ins class="diffchange diffchange-inline"> </ins>G<ins class="diffchange diffchange-inline"> </ins></math>, <ins class="diffchange diffchange-inline">denotamos</ins> <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">colección</ins> <ins class="diffchange diffchange-inline">de</ins> <ins class="diffchange diffchange-inline">nodos</ins> <ins class="diffchange diffchange-inline">de</ins> <math><ins class="diffchange diffchange-inline"> G </ins></math> <ins class="diffchange diffchange-inline">y</ins> <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">colección</ins> <ins class="diffchange diffchange-inline">de</ins> <ins class="diffchange diffchange-inline">flechas</ins> <ins class="diffchange diffchange-inline">por</ins> <math><ins class="diffchange diffchange-inline"> </ins>G_1<ins class="diffchange diffchange-inline"> </ins></math>. <ins class="diffchange diffchange-inline">Estas</ins> <ins class="diffchange diffchange-inline">dos</ins> <ins class="diffchange diffchange-inline">colecciones</ins> <ins class="diffchange diffchange-inline">están</ins> <ins class="diffchange diffchange-inline">conectados</ins>, <ins class="diffchange diffchange-inline">y</ins> <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">gráfica</ins> <ins class="diffchange diffchange-inline">dada</ins> <ins class="diffchange diffchange-inline">su</ins> <ins class="diffchange diffchange-inline">estructura</ins>, <ins class="diffchange diffchange-inline">por</ins> <ins class="diffchange diffchange-inline">dos</ins> <ins class="diffchange diffchange-inline">funciones</ins>: <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">función</ins> <ins class="diffchange diffchange-inline">de fuente</ins> <math><ins class="diffchange diffchange-inline"> </ins>s:<ins class="diffchange diffchange-inline"> </ins>G_1<ins class="diffchange diffchange-inline"> </ins>\<ins class="diffchange diffchange-inline"> </ins>to G_0<ins class="diffchange diffchange-inline"> </ins></math> <ins class="diffchange diffchange-inline">y el objetivo</ins> <ins class="diffchange diffchange-inline">de</ins> <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">función</ins> <math><ins class="diffchange diffchange-inline"> </ins>t:<ins class="diffchange diffchange-inline"> </ins>G_1<ins class="diffchange diffchange-inline"> </ins>\<ins class="diffchange diffchange-inline"> </ins>to G_0<ins class="diffchange diffchange-inline"> </ins></math><ins class="diffchange diffchange-inline"> </ins>.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>No deberemos, en general, necesitar de una de las colecciones para ser un conjunto, pero felizmente aceptamos grandes colecciones; tratar con la teoría de conjuntos paradojas como son y cuando tenemos que hacerlo. Un gráfo donde ambos nodos y flechas son conjuntos se llama "pequeño". Un grafo que contenga una clase se llama "Largo".</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We shall not, in general, require either of the collections to be a set, but will happily accept larger collections; dealing with set-theoretical paradoxes as and when we have to. A graph where both nodes and arrows are sets shall be called ''small''. A graph where either is a class shall be called ''large''.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">If</del> <del class="diffchange diffchange-inline">both</del> <math>G_0</math> <del class="diffchange diffchange-inline">and</del> <math>G_1</math> <del class="diffchange diffchange-inline">are</del> <del class="diffchange diffchange-inline">finite</del>, <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">graph</del> <del class="diffchange diffchange-inline">is called</del> ''<del class="diffchange diffchange-inline">finite</del>''<del class="diffchange diffchange-inline"> too</del>.</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Si</ins> <ins class="diffchange diffchange-inline">los dos</ins> <math><ins class="diffchange diffchange-inline"> </ins>G_0<ins class="diffchange diffchange-inline"> </ins></math> <ins class="diffchange diffchange-inline">y</ins> <math><ins class="diffchange diffchange-inline"> </ins>G_1<ins class="diffchange diffchange-inline"> </ins></math> <ins class="diffchange diffchange-inline">son</ins> <ins class="diffchange diffchange-inline">finitos</ins>, <ins class="diffchange diffchange-inline">el</ins> <ins class="diffchange diffchange-inline">grafo</ins> <ins class="diffchange diffchange-inline">se</ins> <ins class="diffchange diffchange-inline">llama</ins>''<ins class="diffchange diffchange-inline">finito</ins>''<ins class="diffchange diffchange-inline">también</ins>.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''empty graph'' has <math>G_0 = G_1 = \emptyset</math>.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The ''empty graph'' has <math>G_0 = G_1 = \emptyset</math>.</div></td>
</tr>
</table>Carlochesshttps://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&diff=30295&oldid=prevJaimeSoffer at 16:24, 27 September 20092009-09-27T16:24:00Z<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:24, 27 September 2009</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==Bienvenida==</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==Welcome, administratrivia==</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">I'm</del> Mikael Vejdemo-Johansson. <del class="diffchange diffchange-inline">I</del> <del class="diffchange diffchange-inline">can</del> <del class="diffchange diffchange-inline">be</del> <del class="diffchange diffchange-inline">reached</del> <del class="diffchange diffchange-inline">in</del> <del class="diffchange diffchange-inline">my</del> <del class="diffchange diffchange-inline">office</del> 383-BB<del class="diffchange diffchange-inline">, especially</del> <del class="diffchange diffchange-inline">during</del> <del class="diffchange diffchange-inline">my</del> <del class="diffchange diffchange-inline">office</del> <del class="diffchange diffchange-inline">hours;</del> <del class="diffchange diffchange-inline">or</del> <del class="diffchange diffchange-inline">by</del> <del class="diffchange diffchange-inline">email</del> <del class="diffchange diffchange-inline">to</del> mik@math.stanford.edu.</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">El autor original es</ins> Mikael Vejdemo-Johansson. <ins class="diffchange diffchange-inline">Se</ins> <ins class="diffchange diffchange-inline">le</ins> <ins class="diffchange diffchange-inline">puede</ins> <ins class="diffchange diffchange-inline">encontrar</ins> <ins class="diffchange diffchange-inline">en</ins> <ins class="diffchange diffchange-inline">su</ins> <ins class="diffchange diffchange-inline">oficina</ins> 383-BB <ins class="diffchange diffchange-inline">durante</ins> <ins class="diffchange diffchange-inline">horas</ins> <ins class="diffchange diffchange-inline">de</ins> <ins class="diffchange diffchange-inline">oficina</ins> <ins class="diffchange diffchange-inline">o</ins> <ins class="diffchange diffchange-inline">por</ins> <ins class="diffchange diffchange-inline">correo</ins> <ins class="diffchange diffchange-inline">en</ins> mik@math.stanford.edu.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==Introducción==</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>I encourage, strongly, student interactions.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===¿Por qué este curso?===</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Las introducciones a Haskell usualmente incluyen indicaciones de que la Teoría de Categorías es una herramienta útil, aunque no haces mucho más que mencionarlo. El objetivo de este curso es cubrir esa brecha, y proporcionar una introducción a la Teoría de Categorías que se enlace con Haskell y con la programación funcional como fuente de ejemplos y aplicaciones. </div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>I will be out of town September 24 - 29. I will monitor forum and email closely, and recommend electronic ways of getting in touch with me during this week. I will be back again in time for the office hours on the 30th.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===¿Qué incluye?=== </div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==Introduction==</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===Why this course?===</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>An introduction to Haskell will usually come with pointers toward Category Theory as a useful tool, though not with much more than the mention of the subject. This course is intended to fill that gap, and provide an introduction to Category Theory that ties into Haskell and functional programming as a source of examples and applications.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===What will we cover?=== </div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The definition of categories, special objects and morphisms, functors, natural transformation, (co-)limits and special cases of these, adjunctions, freeness and presentations as categorical constructs, monads and Kleisli arrows, recursion with categorical constructs. </div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>La definición de categorías, objetos especiales y morfismos, functores, transformación natural, (co-)límites y casos específicos, adjuntos, libertad y presentación como construcciones categóricas, mónadas y flechas de Kleisli, recursión con construcciones categóricas.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Maybe, just maybe, if we have enough time, we'll finish with looking at the definition of a topos, and how this encodes logic internal to a category. Applications to fuzzy sets.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Maybe, just maybe, if we have enough time, we'll finish with looking at the definition of a topos, and how this encodes logic internal to a category. Applications to fuzzy sets.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===<del class="diffchange diffchange-inline">What</del> <del class="diffchange diffchange-inline">do</del> <del class="diffchange diffchange-inline">we require</del>?===</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===<ins class="diffchange diffchange-inline">¿Qué</ins> <ins class="diffchange diffchange-inline">hace</ins> <ins class="diffchange diffchange-inline">falta</ins>?===</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Los ejemplos provendrán de matemáticas discretas, lógica, programación en Haskell y álgebra lineal. Espero que los siguientes conceptos sean por lo menos vagamente familiares para alguien estudiando este curso:</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Our examples will be drawn from discrete mathematics, logic, Haskell programming and linear algebra. I expect the following concepts to be at least vaguely familiar to anyone taking this course:</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Conjuntos</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Sets</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Funciones</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Functions</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Permutaciones</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Permutations</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <del class="diffchange diffchange-inline">Groups</del></div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins class="diffchange diffchange-inline">Grupos</ins></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Conjuntos parcialmente ordenados</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Partially ordered sets</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Espacios vectoriales</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Vector spaces</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Mapas lineales</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Linear maps</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* Matrices</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* Matrices</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Homomorfismos</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Homomorphisms</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===<del class="diffchange diffchange-inline">Good</del> <del class="diffchange diffchange-inline">references</del>===</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===<ins class="diffchange diffchange-inline">Buenas</ins> <ins class="diffchange diffchange-inline">referencias</ins>===</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>En la biblioteca de matemáticas/CC (Stanford) hay:</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>On reserve in the mathematics/CS library are:</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* ''Mac Lane'': '''Categories for the working mathematician'''</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* ''Mac Lane'': '''Categories for the working mathematician'''</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* ''Awodey'': '''Category Theory'''</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* ''Awodey'': '''Category Theory'''</div></td>
</tr>
<tr>
<td colspan="2" class="diff-lineno">Line 44:</td>
<td colspan="2" class="diff-lineno">Line 39:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Monoids===</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Monoids===</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Para establecer la notación y estar seguros de que todos hayan visto la definición:</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In order to settle notation and ensure everybody's seen a definition before:</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker"><a class="mw-diff-movedpara-right" title="Paragraph was moved. Click to jump to old location." href="#movedpara_49_0_lhs">⚫</a></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><a name="movedpara_47_1_rhs"></a>'''<ins class="diffchange diffchange-inline">Definición</ins>''' <ins class="diffchange diffchange-inline">Un</ins> ''<ins class="diffchange diffchange-inline">monoide</ins>'' <ins class="diffchange diffchange-inline">es</ins> <ins class="diffchange diffchange-inline">un</ins> <ins class="diffchange diffchange-inline">conjunto</ins> <math>M</math> <ins class="diffchange diffchange-inline">equipado</ins> <ins class="diffchange diffchange-inline">con</ins> <ins class="diffchange diffchange-inline">una</ins> <ins class="diffchange diffchange-inline">operación</ins> <ins class="diffchange diffchange-inline">binaria</ins> <ins class="diffchange diffchange-inline">asociativa</ins> <math>*</math> (<ins class="diffchange diffchange-inline">en</ins> Haskell: <hask>mappend</hask>) <ins class="diffchange diffchange-inline">y</ins> <ins class="diffchange diffchange-inline">un</ins> <ins class="diffchange diffchange-inline">elemento</ins> <ins class="diffchange diffchange-inline">identidad</ins> <math>\emptyset</math> (<ins class="diffchange diffchange-inline">en</ins> Haskell: <hask>mempty</hask>).</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Un ''semigrupo'' es un monoide sin el requerimiento de elemento identidad.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"><a class="mw-diff-movedpara-left" title="Paragraph was moved. Click to jump to new location." href="#movedpara_47_1_rhs">⚫</a></td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><a name="movedpara_49_0_lhs"></a>'''<del class="diffchange diffchange-inline">Definition</del>''' <del class="diffchange diffchange-inline">A</del> ''<del class="diffchange diffchange-inline">monoid</del>'' <del class="diffchange diffchange-inline">is</del> <del class="diffchange diffchange-inline">a</del> <del class="diffchange diffchange-inline">set</del> <math>M</math> <del class="diffchange diffchange-inline">equipped</del> <del class="diffchange diffchange-inline">with</del> <del class="diffchange diffchange-inline">a</del> <del class="diffchange diffchange-inline">binary</del> <del class="diffchange diffchange-inline">associative</del> <del class="diffchange diffchange-inline">operation</del> <math>*</math> (<del class="diffchange diffchange-inline">in</del> Haskell: <hask>mappend</hask>) <del class="diffchange diffchange-inline">and</del> <del class="diffchange diffchange-inline">an</del> <del class="diffchange diffchange-inline">identity</del> <del class="diffchange diffchange-inline">element</del> <math>\emptyset</math> (<del class="diffchange diffchange-inline">in</del> Haskell: <hask>mempty</hask>).</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>A ''semigroup'' is a monoid without the requirement for an identity element.</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">A</del> <del class="diffchange diffchange-inline">function</del> <math>f:M\to N</math> <del class="diffchange diffchange-inline">is</del> <del class="diffchange diffchange-inline">a</del> <del class="diffchange diffchange-inline">monoid</del> <del class="diffchange diffchange-inline">homomorphism</del> <del class="diffchange diffchange-inline">if</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">following</del> <del class="diffchange diffchange-inline">conditions</del> <del class="diffchange diffchange-inline">hold</del>:</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Una</ins> <ins class="diffchange diffchange-inline">función</ins> <math>f:M\to N</math> <ins class="diffchange diffchange-inline">es</ins> <ins class="diffchange diffchange-inline">un</ins> <ins class="diffchange diffchange-inline">homomorfismo</ins> <ins class="diffchange diffchange-inline">de</ins> <ins class="diffchange diffchange-inline">monoide</ins> <ins class="diffchange diffchange-inline">si</ins> <ins class="diffchange diffchange-inline">se</ins> <ins class="diffchange diffchange-inline">cumplen</ins> <ins class="diffchange diffchange-inline">las siguientes condiciones</ins>:</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* <math>f(\emptyset) = \emptyset</math></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* <math>f(\emptyset) = \emptyset</math></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* <math>f(m*m') = f(m)*f(m')</math></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* <math>f(m*m') = f(m)*f(m')</math></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==<del class="diffchange diffchange-inline">Category</del>==</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==<ins class="diffchange diffchange-inline">Categoría</ins>==</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===<del class="diffchange diffchange-inline">Graphs</del>===</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===<ins class="diffchange diffchange-inline">Gráficas</ins>===</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">We</del> <del class="diffchange diffchange-inline">recall</del> <del class="diffchange diffchange-inline">the</del> <del class="diffchange diffchange-inline">definition of a</del> ''(<del class="diffchange diffchange-inline">directed</del>)<del class="diffchange diffchange-inline"> graph</del>''. <del class="diffchange diffchange-inline">A</del> <del class="diffchange diffchange-inline">graph</del> <math>G</math> <del class="diffchange diffchange-inline">is</del> <del class="diffchange diffchange-inline">a</del> <del class="diffchange diffchange-inline">collection</del> <del class="diffchange diffchange-inline">of</del> ''<del class="diffchange diffchange-inline">edges</del> (<del class="diffchange diffchange-inline">arrows</del>)'' <del class="diffchange diffchange-inline">and</del> ''<del class="diffchange diffchange-inline">vertices</del> (<del class="diffchange diffchange-inline">nodes</del>)''. <del class="diffchange diffchange-inline">Each</del> <del class="diffchange diffchange-inline">edge</del> <del class="diffchange diffchange-inline">is</del> <del class="diffchange diffchange-inline">assigned</del> <del class="diffchange diffchange-inline">a</del> ''<del class="diffchange diffchange-inline">source</del>'' <del class="diffchange diffchange-inline">node</del> <del class="diffchange diffchange-inline">and</del> <del class="diffchange diffchange-inline">a</del> ''<del class="diffchange diffchange-inline">target</del>''<del class="diffchange diffchange-inline"> node</del>. </div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Recordemos</ins> <ins class="diffchange diffchange-inline">la</ins> <ins class="diffchange diffchange-inline">definición</ins> <ins class="diffchange diffchange-inline">de</ins> ''<ins class="diffchange diffchange-inline">gráfica </ins>(<ins class="diffchange diffchange-inline">dirigida</ins>)''. <ins class="diffchange diffchange-inline">Una</ins> <ins class="diffchange diffchange-inline">gráfica</ins> <math>G</math> <ins class="diffchange diffchange-inline">es</ins> <ins class="diffchange diffchange-inline">una</ins> <ins class="diffchange diffchange-inline">colección de</ins> ''<ins class="diffchange diffchange-inline">aristas</ins> (<ins class="diffchange diffchange-inline">flechas</ins>)'' <ins class="diffchange diffchange-inline">y</ins> ''<ins class="diffchange diffchange-inline">vértices</ins> (<ins class="diffchange diffchange-inline">nodos</ins>)''. <ins class="diffchange diffchange-inline">A</ins> <ins class="diffchange diffchange-inline">cada</ins> <ins class="diffchange diffchange-inline">arista</ins> <ins class="diffchange diffchange-inline">se</ins> <ins class="diffchange diffchange-inline">le asigna un nodo</ins> ''<ins class="diffchange diffchange-inline">fuente</ins>'' <ins class="diffchange diffchange-inline">y</ins> <ins class="diffchange diffchange-inline">un</ins> <ins class="diffchange diffchange-inline">nodo</ins> ''<ins class="diffchange diffchange-inline">destino</ins>''. </div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><math><del class="diffchange diffchange-inline">source</del> \to <del class="diffchange diffchange-inline">target</del></math></div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><math><ins class="diffchange diffchange-inline">fuente</ins> \to <ins class="diffchange diffchange-inline">destino</ins></math></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Given a graph <math>G</math>, we denote the collection of nodes by <math>G_0</math> and the collection of arrows by <math>G_1</math>. These two collections are connected, and the graph given its structure, by two functions: the source function <math>s:G_1\to G_0</math> and the target function <math>t:G_1\to G_0</math>.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Given a graph <math>G</math>, we denote the collection of nodes by <math>G_0</math> and the collection of arrows by <math>G_1</math>. These two collections are connected, and the graph given its structure, by two functions: the source function <math>s:G_1\to G_0</math> and the target function <math>t:G_1\to G_0</math>.</div></td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-30274:rev-30295:1.10.0 -->
</table>JaimeSofferhttps://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&diff=30274&oldid=prevJaimeSoffer: Es/MATH198/Clase 1 moved to Es/Teoría de Categorías y Programación Funcional @ Stanford: Clase 12009-09-26T17:17:05Z<p>Es/MATH198/Clase 1 moved to Es/Teoría de Categorías y Programación Funcional @ Stanford: Clase 1</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:17, 26 September 2009</td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-30273:rev-30274:1.10.0 -->
</table>JaimeSofferhttps://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&diff=30273&oldid=prevJaimeSoffer at 17:15, 26 September 20092009-09-26T17:15:28Z<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:15, 26 September 2009</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>{{Es/Traducción en progreso|titulo=<del class="diffchange diffchange-inline">Guía</del> de <del class="diffchange diffchange-inline">Haskell</del> <del class="diffchange diffchange-inline">para</del> <del class="diffchange diffchange-inline">autoestopistas</del>|original=<del class="diffchange diffchange-inline">Hitchhikers guide to</del> <del class="diffchange diffchange-inline">Haskell</del>}}</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>{{Es/Traducción en progreso|titulo=<ins class="diffchange diffchange-inline">Teoría</ins> de <ins class="diffchange diffchange-inline">Categorías</ins> <ins class="diffchange diffchange-inline">y</ins> <ins class="diffchange diffchange-inline">Programación Funcional: Clase 1</ins>|original=<ins class="diffchange diffchange-inline">User:Michiexile/MATH198</ins> }}</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This page now includes additional information based on the notes taken in class. Hopefully this will make the notes reasonably complete for everybody.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This page now includes additional information based on the notes taken in class. Hopefully this will make the notes reasonably complete for everybody.</div></td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-30272:rev-30273:1.10.0 -->
</table>JaimeSofferhttps://wiki.haskell.org/index.php?title=Es/Teor%C3%ADa_de_Categor%C3%ADas_y_Programaci%C3%B3n_Funcional_@_Stanford:_Clase_1&diff=30272&oldid=prevJaimeSoffer: planeando traducir esto2009-09-26T17:12:44Z<p>planeando traducir esto</p>
<p><b>New page</b></p><div>{{Es/Traducción en progreso|titulo=Guía de Haskell para autoestopistas|original=Hitchhikers guide to Haskell}}<br />
<br />
This page now includes additional information based on the notes taken in class. Hopefully this will make the notes reasonably complete for everybody.<br />
<br />
<br />
==Welcome, administratrivia==<br />
<br />
I'm Mikael Vejdemo-Johansson. I can be reached in my office 383-BB, especially during my office hours; or by email to mik@math.stanford.edu.<br />
<br />
I encourage, strongly, student interactions.<br />
<br />
I will be out of town September 24 - 29. I will monitor forum and email closely, and recommend electronic ways of getting in touch with me during this week. I will be back again in time for the office hours on the 30th.<br />
<br />
==Introduction==<br />
===Why this course?===<br />
<br />
An introduction to Haskell will usually come with pointers toward Category Theory as a useful tool, though not with much more than the mention of the subject. This course is intended to fill that gap, and provide an introduction to Category Theory that ties into Haskell and functional programming as a source of examples and applications.<br />
<br />
===What will we cover?=== <br />
<br />
The definition of categories, special objects and morphisms, functors, natural transformation, (co-)limits and special cases of these, adjunctions, freeness and presentations as categorical constructs, monads and Kleisli arrows, recursion with categorical constructs. <br />
<br />
Maybe, just maybe, if we have enough time, we'll finish with looking at the definition of a topos, and how this encodes logic internal to a category. Applications to fuzzy sets.<br />
<br />
===What do we require?===<br />
<br />
Our examples will be drawn from discrete mathematics, logic, Haskell programming and linear algebra. I expect the following concepts to be at least vaguely familiar to anyone taking this course:<br />
* Sets<br />
* Functions<br />
* Permutations<br />
* Groups<br />
* Partially ordered sets<br />
* Vector spaces<br />
* Linear maps<br />
* Matrices<br />
* Homomorphisms<br />
<br />
===Good references===<br />
<br />
On reserve in the mathematics/CS library are:<br />
* ''Mac Lane'': '''Categories for the working mathematician'''<br />
* ''Awodey'': '''Category Theory'''<br />
<br />
===Monoids===<br />
<br />
In order to settle notation and ensure everybody's seen a definition before:<br />
<br />
'''Definition''' A ''monoid'' is a set <math>M</math> equipped with a binary associative operation <math>*</math> (in Haskell: <hask>mappend</hask>) and an identity element <math>\emptyset</math> (in Haskell: <hask>mempty</hask>).<br />
<br />
A ''semigroup'' is a monoid without the requirement for an identity element.<br />
<br />
A function <math>f:M\to N</math> is a monoid homomorphism if the following conditions hold:<br />
* <math>f(\emptyset) = \emptyset</math><br />
* <math>f(m*m') = f(m)*f(m')</math><br />
<br />
==Category==<br />
<br />
===Graphs===<br />
<br />
We recall the definition of a ''(directed) graph''. A graph <math>G</math> is a collection of ''edges (arrows)'' and ''vertices (nodes)''. Each edge is assigned a ''source'' node and a ''target'' node. <br />
<br />
<math>source \to target</math><br />
<br />
Given a graph <math>G</math>, we denote the collection of nodes by <math>G_0</math> and the collection of arrows by <math>G_1</math>. These two collections are connected, and the graph given its structure, by two functions: the source function <math>s:G_1\to G_0</math> and the target function <math>t:G_1\to G_0</math>.<br />
<br />
We shall not, in general, require either of the collections to be a set, but will happily accept larger collections; dealing with set-theoretical paradoxes as and when we have to. A graph where both nodes and arrows are sets shall be called ''small''. A graph where either is a class shall be called ''large''.<br />
<br />
If both <math>G_0</math> and <math>G_1</math> are finite, the graph is called ''finite'' too.<br />
<br />
The ''empty graph'' has <math>G_0 = G_1 = \emptyset</math>.<br />
<br />
A ''discrete graph'' has <math>G_1=\emptyset</math>.<br />
<br />
A ''complete graph'' has <math>G_1 = \{ (v,w) | v,w\in G_0\}</math>. <br />
<br />
A ''simple graph'' has at most one arrow between each pair of nodes. Any relation on a set can be interpreted as a simple graph.<br />
<br />
* Show some examples.<br />
<br />
A ''homomorphism'' <math>f:G\to H</math> of graphs is a pair of functions <math>f_0:G_0\to H_0</math> and <math>f_1:G_1\to H_1</math> such that sources map to sources and targets map to targets, or in other words:<br />
* <math>s(f_1(e)) = f_0(s(e))</math><br />
* <math>t(f_1(e)) = f_0(t(e))</math><br />
<br />
By a ''path'' in a graph <math>G</math> from the node <math>x</math> to the node <math>y</math> of length <math>k</math>, we mean a sequence of edges <math>(f_1,f_2,\dots,f_k)</math> such that:<br />
* <math>s(f_1)=x</math><br />
* <math>t(f_k)=y</math><br />
* <math>s(f_i) = t(f_{i-1})</math> for all other <math>i</math>.<br />
<br />
Paths with start and end point identical are called ''closed''. For any node <math>x</math>, there is a unique closed path <math>()</math> starting and ending in <math>x</math> of length 0.<br />
<br />
For any edge <math>f</math>, there is a unique path from <math>s(f)</math> to <math>t(f)</math> of length 1: <math>(f)</math>.<br />
<br />
We denote by <math>G_k</math> the set of paths in <math>G</math> of length <math>k</math>. <br />
<br />
===Categories===<br />
<br />
We now are ready to define a category. A ''category'' is a graph <math>C</math> equipped with an associative composition operation <math>\circ:G_2\to G_1</math>, and an identity element for composition <math>1_x</math> for each node <math>x</math> of the graph.<br />
<br />
Note that <math>G_2</math> can be viewed as a subset of <math>G_1\times G_1</math>, the set of all pairs of arrows. It is intentional that we define the composition operator on only a subset of the set of all pairs of arrows - the composable pairs. Whenever you'd want to compose two arrows that don't line up to a path, you'll get nonsense, and so any statement about the composition operator has an implicit "whenever defined" attached to it.<br />
<br />
The definition is not quite done yet - this composition operator, and the identity arrows both have a few rules to fulfill, and before I state these rules, there are some notation we need to cover.<br />
<br />
====Backwards!====<br />
<br />
If we have a path given by the arrows <math>(f,g)</math> in <math>G_2</math>, we expect <math>f:A\to B</math> and <math>g:B\to C</math> to compose to something that goes <math>A\to C</math>. The origin of all these ideas lies in geometry and algebra, and so the abstract arrows in a category are ''supposed'' to behave like functions under function composition, even though we don't say it explicitly.<br />
<br />
Now, we are used to writing function application as <math>f(x)</math> - and possibly, from Haskell, as <hask>f x</hask>. This way, the composition of two functions would read <math>g(f(x))</math>.<br />
<br />
On the other hand, the way we write our paths, we'd read <math>f</math> then <math>g</math>. This juxtaposition makes one of the two ways we write things seem backwards. We can resolve it either by making our paths in the category go backwards, or by reversing how we write function application. <br />
<br />
In the latter case, we'd write <math>x.f</math>, say, for the application of <math>f</math> to <math>x</math>, and then write <math>x.f.g</math> for the composition. It all ends up looking a lot like Reverse Polish Notation, and has its strengths, but feels unnatural to most. It does, however, have the benefit that we can write out function composition as <math>(f,g) \mapsto f.g</math> and have everything still make sense in all notations.<br />
<br />
In the former case, which is the most common in the field, we accept that paths as we read along the arrows and compositions look backwards, and so, if <math>f:A\to B</math> and <math>g:B\to C</math>, we write <math>g\circ f:A\to C</math>, remembering that ''elements'' are introduced from the right, and the functions have to consume the elements in the right order.<br />
<br />
----<br />
<br />
The existence of the identity map can be captured in a function language as well: it is the existence of a function <math>u:G_0\to G_1</math>. <br />
<br />
Now for the remaining rules for composition. Whenever defined, we expect associativity - so that <math>h\circ(g\circ f)=(h\circ g)\circ f</math>. Furthermore, we expect:<br />
# Composition respects sources and targets, so that:<br />
#* <math>s(g\circ f) = s(f)</math><br />
#* <math>t(g\circ f) = t(g)</math><br />
# <math>s(u(x)) = t(u(x)) = x</math><br />
<br />
In a category, arrows are also called ''morphisms'', and nodes are also called ''objects''. This ties in with the algebraic roots of the field.<br />
<br />
We denote by <math>Hom_C(A,B)</math>, or if <math>C</math> is obvious from context, just <math>Hom(A,B)</math>, the set of all arrows from <math>A</math> to <math>B</math>. This is the ''hom-set'' or ''set of morphisms'', and may also be denoted <math>C(A,B)</math>.<br />
<br />
If a category is large or small or finite as a graph, it is called a large/small/finite category.<br />
<br />
A category with objects a collection of sets and morphisms a selection from all possible set-valued functions such that the identity morphism for each object is a morphism, and composition in the category is just composition of functions is called ''concrete''. Concrete categories form a very rich source of examples, though far from all categories are concrete.<br />
<br />
===New Categories from old===<br />
<br />
As with most other algebraic objects, one essential part of our tool box is to take known objects and form new examples from them. This allows us generate a wealth of examples from the ones that shape our intuition.<br />
<br />
Typical things to do here would be to talk about ''subobjects'', ''products'' and ''coproducts'', sometimes obvious ''variations on the structure'', and what a ''typical object'' looks like. Remember from linear algebra how ''subspaces'', ''cartesian products'' (which for finite-dimensional vectorspaces covers both products and coproducts) and ''dual spaces'' show up early, as well as the theorems giving ''dimension'' as a complete descriptor of a vectorspace.<br />
<br />
We'll go through the same sequence here; with some significant small variations.<br />
<br />
A category <math>D</math> is a ''subcategory'' of the category <math>C</math> if:<br />
* <math>D_0\subseteq C_0</math><br />
* <math>D_1\subseteq C_1</math><br />
* <math>D_1</math> contains <math>1_X</math> for all <math>X\in D_0</math><br />
* sources and targets of all the arrows in <math>D_1</math> are all in <math>D_0</math><br />
* the composition in <math>D</math> is the restriction of the composition in <math>C</math>.<br />
<br />
Written this way, it does look somewhat obnoxious. It does become easier though, with the realization - studied closer in homework exercise 2 - that the really important part of a category is the collection of arrows. Thus, a subcategory is a subcollection of the collection of arrows - with identities for all objects present, and with at least all objects that the existing arrows imply.<br />
<br />
A subcategory <math>D\subseteq C</math> is ''full'' if <math>D(A,B)=C(A,B)</math> for all objects <math>A,B</math> of <math>D</math>. In other words, a full subcategory is completely determined by the selection of objects in the subcategory.<br />
<br />
A subcategory <math>D\subseteq C</math> is ''wide'' if the collection of objects is the same in both categories. Hence, a wide subcategory picks out a subcollection of the morphisms.<br />
<br />
The ''dual'' of a category is to a large extent inspired by vector space duals. In the dual <math>C^*</math> of a category <math>C</math>, we have the same objects, and the morphisms are given by the equality <math>C^*(A,B)=C(B,A)</math> - every morphism from <math>C</math> is present, but it goes in the ''wrong'' direction. Dualizing has a tendency to add the prefix ''co-'' when it happens, so for instance coproducts are the dual notion to products. We'll return to this construction many times in the course. <br />
<br />
Given two categories <math>C,D</math>, we can combine them in several ways:<br />
# We can form the category that has as objects the disjoint union of all the objects of <math>C</math> and <math>D</math>, and that sets <math>Hom(A,B)=\emptyset</math> whenever <math>A,B</math> come from different original categories. If <math>A,B</math> come from the same original category, we simply take over the homset from that category. This yields a categorical ''coproduct'', and we denote the result by <math>C+D</math>. Composition is inherited from the original categories.<br />
# We can also form the category with objects <math>\langle A,B\rangle</math> for every pair of objects <math>A\in C, B\in D</math>. A morphism in <math>Hom(\langle A,B\rangle,\langle A',B'\rangle)</math> is simply a pair <math>\langle f:A\to A',g:B\to B'\rangle</math>. Composition is defined componentwise. This category is the categorical correspondent to the cartesian ''product'', and we denot it by <math>C\times D</math>.<br />
<br />
In these three constructions - the dual, the product and the coproduct - he arrows in the categories are formal constructions, not functions; even if the original category was given by functions, the result is no longer given by a function.<br />
<br />
Given a category <math>C</math> and an object <math>A</math> of that category, we can form the ''slice category'' <math>C/A</math>. Objects in the slice category are arrows <math>B\to A</math> for some object <math>B</math> in <math>C</math>, and an arrow <math>\phi:f\to g</math> is an arrow <math>s(f)\to s(g)</math> such that <math>f=g\circ\phi</math>. Composites of arrows are just the composites in the base category. <br />
<br />
Notice that the same arrow <math>\phi</math> in the base category <math>C</math> represents potentially many different arrows in <math>C/A</math>: it represents one arrow for each choice of source and target compatible with it.<br />
<br />
There is a dual notion: the ''coslice category'' <math>A\backslash C</math>, where the objects are paired with maps <math>A\to B</math>.<br />
<br />
Slice categories can be used, among other things, to specify the idea of parametrization. The slice category <math>C/A</math> gives a sense to the idea of ''objects from <math>C</math> labeled by elements of <math>A</math>''.<br />
<br />
We get this characterization by interpreting the arrow representing an object as representing its source and a ''type function''. Hence, in a way, the <hask>Typeable</hask> type class in Haskell builds a slice category on an appropriate subcategory of the category of datatypes.<br />
<br />
Alternatively, we can phrase the importance of the arrow in a slice categories of, say, Set, by looking at preimages of the slice functions. That way, an object <math>f:B\to A</math> gives us a family of (disjoint) subsets of <math>B</math> ''indexed'' by the elements of <math>A</math>.<br />
<br />
Finally, any graph yields a category by just filling in the arrows that are missing. The result is called the ''free category generated by the graph'', and is a concept we will return to in some depth. Free objects have a strict categorical definition, and they serve to give a model of thought for the things they are free objects for. Thus, categories are essentially graphs, possibly with restrictions or relations imposed; and monoids are essentially strings in some alphabet, with restrictions or relatinos.<br />
<br />
===Examples===<br />
<br />
* The empty category.<br />
** No objects, no morphisms.<br />
* The one object/one arrow category <math>1</math>.<br />
** A single object and its identity arrow.<br />
* The categories <math>2</math> and <math>1+1</math>.<br />
** Two objects, <math>A,B</math> with identity arrows and a unique arrow <math>A\to B</math>.<br />
* The category Set of sets.<br />
** Sets for objects, functions for arrows.<br />
* The catgeory FSet of finite sets.<br />
** Finite sets for objects, functions for arrows.<br />
* The category PFn of sets and partial functions.<br />
** Sets for objects. Arrows are pairs <math>(S'\subseteq S,f:S'\to T)\in PFn(S,T)</math>.<br />
** <math>PFn(A,B)</math> is a partially ordered set. <math>(S_f,f)\leq(S_g,g)</math> precisely if <math>S_f\subseteq S_g</math> and <math>f=g|_{S_f}</math>.<br />
* There is an alternative way to define a category of partial functions: For objects, we take sets, and for morphisms <math>S\to T</math>, we take subsets <math>F\subseteq S\times T</math> such that each element in <math>S</math> occurs in at most one pair in the subset. Composition is by an interpretation of these subsets corresponding to the previous description. We'll call this category <math>PFn'</math>.<br />
* Every partial order is a category. Each hom-set has at most one element.<br />
** Objects are the elements of the poset. Arrows are unique, with <math>A\to B</math> precisely if <math>A\leq B</math>.<br />
* Every monoid is a category. Only one object.<br />
*** Kleene closure. Free monoids. <br />
* The category of Sets and injective functions.<br />
* The category of Sets and surjective functions.<br />
* The category of <math>k</math>-vector spaces and linear maps.<br />
* The category with objects the natural numbers and <math>Hom(m,n)</math> the set of <math>m\times n</math>-matrices. <br />
* The category of Data Types with Computable Functions.<br />
** Our ideal programming language has:<br />
*** Primitive data types.<br />
*** Constants of each primitive type.<br />
*** Operations, given as functions between types. <br />
*** Constructors, producing elements from data types, and producing derived data types and operations.<br />
** We will assume that the language is equipped with<br />
*** A do-nothing operation for each data type. Haskell has <hask>id</hask>.<br />
*** An empty type <math>1</math>, with the property that each type has exactly one function to this type. Haskell has <hask>()</hask>. We will use this to define the constants of type <math>t</math> as functions <math>1\to t</math>. Thus, constants end up being 0-ary functions.<br />
*** A composition constructor, taking an operator <math>f:A\to B</math> and another operator <math>g:B\to C</math> and producing an operator <math>g\circ f:A\to C</math>. Haskell has <hask>(.)</hask>. <br />
** This allows us to model a functional programming language with a category.<br />
* The category with objects logical propositions and arrows proofs.<br />
* The category Rel has objects finite sets and morphisms <math>A\to B</math> being subsets of <math>A\times B</math>. Composition is by <math>(a,c)\in g\circ f</math> if there is some <math>b\in B</math> such that <math>(a,b)\in f, (b,c)\in g</math>. Identity morphism is the diagonal <math>(a,a): a\in A</math>.<br />
<br />
<br />
<br />
<br />
<br />
===Homework===<br />
<br />
For a passing mark, a written, acceptable solution to at least 3 of the 6 questions should be given no later than midnight before the next lecture.<br />
<br />
For each lecture, there will be a few exercises marked with the symbol *. These will be more difficult than the other exercises given, will require significant time and independent study, and will aim to complement the course with material not covered in lectures, but nevertheless interesting for the general philosophy of the lecture course.<br />
<br />
# Prove the general associative law: that for any path, and any bracketing of that path, the same composition may be found.<br />
# Which of the following form categories? Proof and disproof for each:<br />
#* Objects are finite sets, morphisms are functions such that <math>|f^{-1}(b)|\leq 2</math> for all morphisms f, objects B and elements b.<br />
#* Objects are finite sets, morphisms are functions such that <math>|f^{-1}(b)|\geq 2</math> for all morphisms f, objects B and elements b.<br />
#* Objects are finite sets, morphisms are functions such that <math>|f^{-1}(b)|<\infty</math> for all morphisms f, objects B and elements b.<br />
# Suppose <math>u:A\to A</math> in some category <math>C</math>. <br />
## If <math>g\circ u=g</math> for all <math>g:A\to B</math> in the category, then <math>u=1_A</math>.<br />
## If <math>u\circ h=h</math> for all <math>h:B\to A</math> in the category, then <math>u=1_A</math>.<br />
## These two results characterize the objects in a category by the properties of their corresponding identity arrows completely.<br />
# For as many of the examples given as you can, prove that they really do form a category. Passing mark is at least 60% of the given examples.<br />
#* Which of the categories are subcategories of which other categories? Which of these are wide? Which are full?<br />
# For this question, all parts are required:<br />
## For which sets is the free monoid on that set commutative.<br />
## Prove that for any category <math>C</math>, the set <math>Hom(A,A)</math> is a monoid under composition for every object <math>A</math>.<br />
# * Read up on <math>\omega</math>-complete partial orders. Suppose <math>S</math> is some set and <math>\mathfrak P</math> is the set of partial functions <math>S\to S</math> - in other words, an element of <math>\mathfrak P</math> is some pair <math>(S_0,f:S_0\to S)</math> with <math>S_0\subseteq S</math>. We give this set a poset structure by <math>(S_0,f)\leq(S_1,g)</math> precisely if <math>S_0\subseteq S_1</math> and <math>f(s)=g(s)\forall s\in S_0</math>.<br />
#* Show that <math>\mathfrak P</math> is a strict <math>\omega</math>-CPO.<br />
#* An element <math>x</math> of <math>S</math> is a ''fixpoint'' of <math>f:S\to S</math> if <math>f(x)=x</math>. Let <math>\mathfrak N</math> be the <math>\omega</math>-CPO of partially defined functions on the natural numbers. We define a function <math>\phi:\mathfrak N\to\mathfrak N</math> by sending some <math>h:\mathbb N\to\mathbb N</math> to a function <math>k</math> defined by<br />
#*# <math>k(0) = 1</math><br />
#*# <math>k(n)</math> is defined only if <math>h(n-1)</math> is defined, and then by <math>k(n)=n*h(n-1)</math>.<br />
:Describe <math>\phi(n\mapsto n^2)</math> and <math>\phi(n\mapsto n^3)</math>. Show that <math>\phi</math> is ''continuous''. Find a fixpoint <math>(S_0,f)</math> of <math>\phi</math> such that any other fixpoint of the same function is less than this one.<br />
:Find a continuous endofunction on some <math>\omega</math>-CPO that has the fibonacci function <math>F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)</math> as the least fixed point.<br />
:Implement a Haskell function that finds fixed points in an <math>\omega</math>-CPO. Implement the two fixed points above as Haskell functions - using the <math>\omega</math>-CPO fixed point approach in the implementation. It may well be worth looking at <hask>Data.Map</hask> to provide a Haskell context for a partial function for this part of the task.</div>JaimeSoffer