Dear Leetcode

Thank you for adding Scala into your coding platform. I found it to be a great tool to learn Scala, particularly it's standard library. Potentially, I think Leetcode code be a great place to learn functional programming since people can practice coding hundreds of questions using Scala. I want this improve this learning experience even more by suggesting to add the Category Theory libraries, Cats and Scalaz, to the Scala platform. Many beautiful and elegant abstractions in functional programming languages, such as Haskell, can be made using these Category Theory techniques.

These Category Theory libraries are starting to become more prevalent in the industry and companies are heavily endorsing them. Many large companies, such as Stripe and eBay, are using these libraries. Having these libraries on the Leetcode platform could bring an opportunity for interviewees to learn these uprising techniques and have an easier time transitioning into a job.

Also, using these Category Theory techniques during an interview can give leverage to an interviewee. Using these abstract primitives shows the interviewers that the interviewee can write concise and immutable code, which conveys to the interviewer that the interviewee has a good grasp of creating abstractions and can learn new frameworks quickly. It can also give the interviewee leverage to teach the interviewer something new as most interviewers do not know category theory. Not only could this give them "bonus points" for explaining an interviewer something new, but could potentially entice them to learn category theory. As an interviewee uses category theory more, it helps them land a job offer, which in hand, encourage more of their friends to use Leetcode to help them get job offers.

I've even noticed at times that I want to use these Category Theory techniques when I am solving LeetCode questions. When I am answering questions involving graphs, it can be quite cumbersome to solve graph-related problems in a type-safe manner. Often, your chains of computation can get tangled and messy quite quickly, leading you to get confused, especially if your answer gets rejected and you are trying to fix it. Suppose that you are trying to compute the smallest distance between node i among nodes j1,j2,..jn in a tree-like directed graph data structure with positive weights. Computing the min distance in the tree would normally look like the following:

type Graph = immutable.Map[Int, immutable.Map[Int, Int]]
    
    def minDistanceBad(g: Graph, i: Int, nodes: Set[Int]): Option[Int] = {
        g.getOrElse(i, Map.empty).foldLeft(None: Option[Int])({
          case (Some(minDistance), (dest, dist)) =>
            if (!nodes.contains(dest))
              minDistanceBad(g, dest, nodes).map(math.min(_ + dist, minDistance)).orElse(Some(minDistance))
            else
              Some(math.min(minDistance, dist))
          case (None, (dest, dist)) => if (nodes.contains(dest)) Some(dist) else minDistanceBad(g, dest, nodes).map(_ + dist)
        })
      }

You can see that the computation often leads to a lot of nested chains with lines of code with long chained statements. From my experience, you would often have to use foldLeft, which can have many nested statements along with folding over complicated accumulative state.

This code can be simplified if we include Cats into the picture and using the implicit type classes feature in Scala. Here is how the min distance computation would look like:

type Graph = immutable.Map[Int, immutable.Map[Int, Int]]

implicit class GraphExtensions(val g: Graph) {
  def edges(i: Int): List[(Int, Int)] = {
    g.getOrElse(i, immutable.HashMap.empty).toList
  }
}

implicit val monoidalDistanceSum: Monoid[Option[Int]] = new Monoid[Option[Int]] {
  def combine(x: Option[Int], y: Option[Int]): Option[Int] = (x, y) match {
    case (Some(x), Some(y)) => x.min(y).pure
    case (x, y) => x.orElse(y)
  }

  def empty: Option[Int] = None
}

def minDistance(g: Graph, i: Int, nodes: Set[Int]): Option[Int] = {
  g.edges(i).foldMap(
    ((dest: Int, dist: Int) => 
		(Option.when(nodes.contains(dest))(dest) orElse minDistance(g, dest, nodes))
      .map(_ + dist)).tupled
  )
}

Even though this has more code compared to the original example, we can leverage Cats to make make our computation more modular, making it easier to read and debug in the future. Namely, we see that computing the minimum distance among edges forms a monoid for a given graph. Exploiting the fact that this computation is a monoid allows us to get other constructs for free. In this example, we can use foldMap for free, which enables us to sequentially map each the edges, (k, j) into a distance and then use the monoid to find the accumulative minimized distance over the fold.

Using these Category Theory libraries, Cat and Scalaz, can be extremely useful for a programmer. I hope that Leetcode can include these libraries and help spread the usage of Category Theory. Including these Category Theory libraries can be quite easy. If you are using the sbt build manager to run your scala programs, you can include this line to your build.sbt file:

libraryDependencies += "org.typelevel" %% "cats-core" % "2.0.0"
libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.2.30"