**Algebraic Data Types**

- You can treat algebraic equations like composite types, and vice-versa

**Discrete Category**

- “How do we represent a single set as a category?”
- Sets do not have structure, but morphisms between objects imply structure
- Category in which there are no morphisms beyond identity ones

**Functors**

- A functor maps one category into another
- A functor maps an object in one category into an object in another
- A functor also maps each MORPHISM in one category into a morphism in another
- A functor maps the homset (set of morphisms between any pair of points) of one category into another
- e.g. homset for category C, C(a, b) and a homset for category D, D(fa, fb)

- A functor is a potentially huge number of separate functions
- One big function that maps objects in one category to those in the other
- One function per morphism in the homset that maps each morphism to the other morphism in corresponding homset (?)

- Functor has to preserve structure
- Structure is defined in a category through composition
- COMPOSITIONS must also be mapped by functor

- Information can be added/lost (through non-injective, non-surjective morphisms) but structure must be preserved
- ‘Faithful’ functor
- Injective on homsets

- ‘Full’ functor
- Surjective on homsets

- ‘Fully faithful’ functor

- ‘Faithful’ functor
- Endofunctors
- Mapping within one category
- Then aren’t all morphisms functors?!
**OK: Not all morphisms “map”, not all morphisms are functions, some are relations, and there are other kinds of morphisms too**

- Most functors used in programming deal with only one category – that of sets and types

**Functors in Programming**

- Objects are types
- Morphisms are functions
- A functor is a mapping of types
- A functor is a total mapping – every object and morphism must be mapped
- In Haskell these are ‘type constructors’
- A functor must also map functions
- Even after all mappings been defined, does it meet the conditions (functor laws)?
- Every functor must preserve
- Composition
- Identity

- Every functor must preserve
- Intuition
- Functors as containers

Advertisements