8Easy Categories for Programmers I. Prior Art

(Part I: Prior Art,
 Part II: Meet Categories
 Part III: Examples and Features,
 Part IV: Functors and Morphisms,
 Part V: Some Limits,
 Part VI: Pullback,
 Part VII: Pushout, Union,
 Part VIII: 0, 1, Xn,
 Part IX: Limits in General,
 Part X: Colimits,
google project: http://code.google.com/p/categories)

1. Backgrounds

I'm going to talk about categories. Categories in general are not defined in terms of sets; categories that are sets are called "small categories".
But for the sake of simplicity I'm going to use sets, in most cases. More, the code examples will use finite enumerable sets. Everybody knows, or thinks that knows, what "finite" means; "enumerable" means (assuming boolean logic) that there is a recursive algorithm generating all the elements of the set.

This is the main difference between sets defined in libraries like in Java or Scala and sets in general: general sets, e.g. those defined by Zermelo axioms, can be expressed in code as predicates; since there is no reasonable way to list all objects that satisfy a given predicate, all calculations become either impossible or extremely inefficient. We should not worry about it, though. Quoting my colleague OD, "For an average coder a 'set' is a kind of a data structure, not fancy stuff Zermelo wrote about." (See more of his comments here.)

Also, we have to remember that maintaining set-theoretical integrity in Java or Scala library sets is not a realistic task. Look at this piece of Java code:

Set<Set<?>> ss1 = new HashSet<Set<?>>();

Set<Set<?>> ss2 = new HashSet<Set<?>>();

Set<Integer> si = new HashSet<Integer>() {{ add(0); }};

ss1.add(si);

ss1.add(ss1);

ss1.add(ss2);

ss2.add(si);

ss2.add(ss1);

System.out.println(ss1);

It'll produce stack overflow; this would not happen if we had a true set theory (e.g. ZF); but checking this takes too much time. We don't have that much time. (actually we do, but if we admit it, then our competitors win.)

Another question is, how do we represent mappings from one set to another. We can have a function type with given domain (where the function as defined) and codomain (where the function takes values) types; or we can use Map<From,To>, or we could be very set-theoretical and use sets of pairs satisfying certain conditions. The main motivation in choosing one over the other is convenience; it is not apriori obvious which approach is more convenient; we probably will have to combine all three.

Java lacks some helpful classes; I'll be adding them here when needed.

Note For Programmers

Why would a programmer be interested in categories? Well, without categories, Haskell and all that new stuff is more or less incomprehensible. But I hope to go ahead way beyond, to toposes and topos logic. To learn all this, you'll need to have categories behind your belt as a pretty simple and convenient tool for representing objects and their relationships.

The source code is stored here: http://myjavatools.com/projects/Category/source.zip. There's actually more code in the archive than what is published here. Let me know if you have problems working with the code.

Don't forget to set '-ea' jvm parameter, to enable asserts.

Note For Mathematicians

You probably won't find anything new here. Note that while I use the term "set", I actually do not rely on any particular set theory or computational theory; the code here is not expected to run on Turing machines; more, if you think Turing, you should rather think Heyting. It's a different universe. For instance, a set (or an object) A is finite if any subset of A that is isomorphic to A equals A. Why do I say "object", not "set"? Because sets are not needed here; it's enough if it is discrete objects in a topos. Being discrete is not needed too, but the users will get scared to death if we start offering them half-units or double rings that do not satisfy the AC even for two elements (for which I have to thank professor Andre Scedrov).

Note For Readers

I am very, very thankful to all the good people that read it and make comments (let me know, guys, if you want your "real" names disclosed): OD, warrior, smalgin, igor sereda, Кристофер Робин, Eugene Kirpichov, nivanych, 109, faceted_jacinth...

There are many sources explaining category stuff in details. This article is good, although not always correct; I would rather recommend the classical "Categories for the Working Mathematician" by S.MacLane.

Java Code

Here are some classes we will need later on:

package math.cat;

import java.util.*;


/**
 * Base tools used in this package.
 *
 * All code is <a href="http://myjavatools.com/projects/Category/source.zip">here</a>
 *
 * Credits: http://antilamer.livejournal.com/245962.html
 */

public class Base {
  public static <T> Set<T> Set(T... elements) {
    return new HashSet<T>(Arrays.asList(elements));
  }

  public static <T> T[] array(T... elements) {
    return elements;
  }

  public static <K,V> Map<K,V> Map(final K[] keys, final V[] values) {
    assert keys.length == values.length;
    Map<K,V> map = new HashMap<K,V>();
    for (int i = 0; i < keys.length; i++) {
      map.put(keys[i], values[i]);
    }
    return Collections.unmodifiableMap(map);
  }

  /**
   * Extracts a set from a string as produced by Set.toString().
   * Entries in the set can not be empty strings and cannot contain commas.
   *
   * @param s the string
   * @return restored set
   */
  public static Set<String> parseSet(String s) {
    String[] content = s.substring(1, s.length() - 1).split(",\\s*");
    Set<String> result = new HashSet<String>();
    for (String entry : content) {
      String trimmed = entry.trim();
      if (!trimmed.isEmpty()) result.add(trimmed);
    }
    return result;
  }
}

2. PoSet

Before categories, let's play with simpler structures (but slightly more complicated than just sets); partial order (or poset, partially-ordered set) is the simplest. In Java there is a class named SortedSet; in such a class every elements are comparable. Not so in partial order.

Definition

Partially-ordered set is a set and a binary relationship that is reflexive, transitive and antisymmetric. That is, we have three rules:

• x <= x
• if x <= y && y <= z, then x <= z
• if x <= y && y <= x, then x == y

Examples

Any set X can be considered partially-ordered: no order at all is a partial order.
Natural numbers, where order is defined as this:  a <= b if b is divisible by a.
If (X, <=) is a partial order, the opposite, (X, >=) is also a partial order.

Java Code

package math.cat;

import java.util.*;

import static math.cat.Pair.*;
import math.cat.Pair;

/**
 * Sample Implementation of partially ordered set.
 * All code is <a href="http://myjavatools.com/projects/Category/source.zip">here</a>
 */
public abstract class PoSet<T> extends AbstractSet<T> {
  private final Set<T> elements;

  /*
   * Java technicalities: have to override these methods.
   */
  @Override public Iterator<T> iterator() {  return elements.iterator(); }
  @Override public int size() { return elements.size(); }
  @Override public int hashCode() { return elements.hashCode(); }
  @Override public boolean equals(Object o) { return o instanceof PoSet && ((PoSet)o).equals(this); }

  /**
   * Defines partial order.
   * @param x first compared element
   * @param y second compared element
   * @return true if x is before y in this partial order
   */
  public abstract boolean _le_(T x, T y);

  /**
   * Basic constructor. You need to define a comparator method to build an instance.
   * @param elements elements of this poset.
   */
  public PoSet(Set<T> elements) {
    this.elements = elements;
    validate();
  }

  /**
   * Validates the axioms of this partially ordered set
   */
  private void validate() {
    for(T x : elements) {
      assert _le_(x, x): " reflexivity broken at " + x;

      for (T y : elements) {
        if (_le_(x, y)) {
          if (_le_(y, x)) assert x.equals(y) : "antisymmetry broken at " + x + ", " + y;

          for (T z : elements) {
            if (_le_(y, z)) assert _le_(x, z) : "transitivity broken at " + x + ", " + y + ", " + z;
          }
        }
      }
    }
  }

  /**
   * Two posets are equal if they have the same elements and partial order is the same.
   *
   * @param other other poset to compare
   * @return true if these two posets are equal
   */
  private boolean equals(PoSet<T> other) {
    boolean isEqual = elements.equals(other.elements);
    for (T a : elements) for (T b : elements) {
      isEqual = isEqual && (_le_(a, b) == other._le_(a, b));
    }
    return isEqual;
  }
}

Here's how we could build a poset:

    PoSet<String> ex1 = new PoSet<String>(Set("abc", "def", "ab", "defgh")) {
      public boolean _le_(String a, String  b) {
        return b.indexOf(a) >= 0;
      }
    };

3. Graphs

Definition

There are many different flavors of graphs. Here we deal with what some people call directed multigraph: we are given a set of nodes N and a set of edges (or arrows) A; each edge (arrow) originates at a node and ends at a node. An arrow (edge) may end at the same node where it originated, but not necessarily; there can be any number of arrows leading from one node to another.

Seems like the mainstream notion of graph is when there's not more than one arrow from one node to another; and quite often "graph" means undirected graph, that is, a set of nodes  N and a symmetric non-reflexive binary relationship R ⊂ N×N that defines which nodes are connected. A pedestrian driver example is San Francisco: an undirected graph consists of two-way streets, and a directed graph consists of one-way streets.

From categorical point of view, though, directed multigraphs make more sense.

I use an unusual (for a graph-theorist) notation: source and target of an arrow are returned by functions called d0 and d1. In category theory source is called domain, and target is called codomain. The notation, d0 and d1, comes from so-called internal categories (we'll touch them later on) - that's my excuse for using confusing terms.

Example

Take three sets: an empty set 0, a singleton 1, and a two-element set 2 (consisting of elements named a and b). How many mappings can we find between these three?

Let's start with 0, an empty set. An empty set is a subset of any other, so there's just one function from 0 to each of the three, the inclusion. Also, there could be no function from a non-empty map to an empty one.
Then take 1. A function from a single-element set to another set represents an element of that set; so we have an identity map id:1->1, and two maps to the two-element set 2, correspoinding to its elements, a and b.
Now take 2. It has a trivial function (2.1) to 1. Then what are all possible functions from a two-element set to itself? id, an identity, then swap, the one that swaps a and b; and then there are two functions that maps both source elements to the same target element (a or b) It is probably obvious that any set can be considered a graph with an empty set of arrows.

It is probably obvious that any set can be considered a graph with an empty set of arrows.

Another generic example is a poset treated as a graph: elements of the poset become nodes, and arrows are pairs (x,y) such that x<=y in the poset.

Edit this page (if you have permission) |

Google Docs -- Web word processing, presentations and spreadsheets.