Sketch of first Category Theory exercise for Lambda Jam.

Exercise1.scala

package kenbot.yowcat


/**
 * Lets start with this representation of a category.
 *
 * Ordinarily we'd make better use of the type system here, 
 * but we want to manipulate all these concepts at the value level.
 * 
 * Throughout, we'll use scala.Stream to represent sets or collections in the mathematical sense, even though they don't guarantee uniqueness.
 *
 * To keep things simple, we'll use the standard JVM equality operator '==' to compare things. 
 * 
 */
trait Cat {

  // 1. Objects 
  // Can represent anything at all.  
  type Obj
  def objects: Stream[Obj]

  // 2. Arrows
  // Can represent anything at all.
  type Arr
  def arrows: Stream[Arr]

  // 3. Get the domain of an arrow; the "A" in "A -> B" 
  def dom(f: Arr): Obj

  // 4. Get the codomain of an arrow; the "B" in "A -> B"
  def cod(f: Arr): Obj


  // 5. Composition 
  // Must be associative: a*(b*c) == (a*b)*c  
  final def compose(f: Arr, g: Arr): Arr = { 
    assert(canCompose(f, g))
    comp(f, g) 
  }

  protected[this] def comp(f: Arr, g: Arr): Arr

  final def canCompose(f: Arr, g: Arr): Boolean = 
    dom(f) == cod(g) 


  // 6. Identity
  // Must be neutral when composed from the left or right: 
  // id*a = a*id = a
  def id(obj: Obj): Arr

}


/** 
 * Exercise 1: 
 *
 * Implement the category of JVM Classes and subtype-relationships.
 *
 * What are the objects, and what are the arrows?
 */
object Exercise1 {

  // Let's introduce some syntax sugar for testing
  // a subtype relation; a <:< b
  implicit class SubtypeSugar(thisClass: Class[_]) {
    def <:<(other: Class[_]): Boolean = 
      other isAssignableFrom thisClass
  }

  // Example usage: 
  def isFruitFood: Boolean = classOf[Fruit] <:< classOf[Food] 


  val setOfClasses: Stream[Class[_]] = Stream(
    classOf[Food], classOf[Fruit], classOf[Banana], 
    classOf[Cumquat], classOf[Grape], classOf[Meat], 
    classOf[Yak], classOf[Goat], classOf[Kangaroo], 
    classOf[Tool], classOf[Spanner], classOf[Hammer])

  
  object ClassesSubtypesCategory extends Cat {

    type Obj = Class[_] 
    
    // For argument's sake, let's just say that 
    // these are the only Classes that exist:
    def objects: Stream[Obj] = setOfClasses

    /** 
     * Exercise 1a. 
     * 
     * How could we represent the arrows - subtype relations 
     * between classes?
     *
     * How can we construct the set (ie Stream) of them? 
     */
    type Arr = ???
    def arrows: Stream[Arr] = ???

    /** 
     * Exercise 1b. 
     * 
     * How can we get the domain and codomain objects for an arrow?
     */
    def dom(obj: Class[_]): Arr = ??? 
    def cod(obj: Class[_]): Arr = ???

    /**
     * Exercise 1c. Identity 
     *
     * Produce a representation of the fact that 
     * a class is its own subtype.
     *
     * Composing with any other subtyping relationship must just
     * return the other one.
     */
    def id(obj: Class[_]): Arr = ???

    /**
     * Exercise 1d. Composition 
     *
     * How can we compose our representation of 
     * subtype relationships between classes?
     *
     * Arguments:
     *    g      f
     * A ---> B ---> C
     *
     * Returning:
     * A ----------> C
     * 
     * (Don't forget to make it associative!)
     */
    def comp(f: Arr, g: Arr): Arr = ???

  }

}