Cats, Cats, Cats!

This week was supposed to be my first week at Twitter. Unfortunately, there was a shipping snafu and my laptop ended up getting delayed by a week. This meant that my start date was pushed back to tomorrow (June 7), and I had another week of unstructured life.

Cats

I received the following message from Adam on Thursday:

… I’m going camping this weekend and need someone to catsit Soccers… (emphasis my own)

Soccers is short for Socrates, which is the name of Adam’s cat. I had only seen and heard Socrates virtually. He’d often meow very loudly or jump across Adam’s webcam during our late-night 539 project sessions. The fact that I would be able to meet him in person was probably one of the highlights of my week.

I visited Adam’s place on Friday morning. Socrates was remarkably friendly; he didn’t appear to dislike being picked up by me and on occasion, actually headbutted me.

I despise taking photos of myself, but I made an exception this time. I couldn’t resist having a photo of Socrates on my shoulder like some furry, four-legged parrot. Man, I fucking love cats.

Parts of Saturday and this morning were spent going over to Adam’s (luckily, he lives a 5 minute bus ride away) and making sure Socrates had enough to eat and drink. It was also spent trying to earn his affection. I’d eventually like to get a cat one day, but I’ll wait until my living situation becomes a bit more permanent.

Cats (the Scala library)

Having a week of unstructured time basically meant that I went back to my old ways: reading source code and trying to kill time. This week, I decided to jump into the cats functional programming library for Scala. To motivate this, I refactored some functions that I wrote earlier this year using some of the new features afforded by cats.

I wrote a very lightweight API for storing images back in January as part of an interview for Shopify. They said I could use any language/framework I wanted, so I decided to use Scala and the Scalatra web framework. I hate frontend work, so I only created a backend service. The function below fetches the metadata for images belonging to a certain author:

override def getImageMetadataByAuthor(
  author: String
): Future[Either[CollectionError, Seq[Metadata]]] =
  for {
    imagesByAuthor <- getImagesByAuthor(author)
    eitherMetadata <- Future.sequence(imagesByAuthor.map(getImageMetadata))
  } yield
    if (eitherMetadata.forall(_.isRight)) Right(eitherMetadata.flatMap(_.toSeq))
    else Left(LookupError(s"Error while looking up metadata for author: $author"))

At a high level, what this code does is:

1. Query a database to get a list of ids of images by a given author (imagesByAuthor)
2. For every id in the list from (1), map a call to getImageMetadata, which eventually returns either an error or a metadata object (Either[CollectionError, Metadata])
3. If all the operations were successful return the collapsed list of metadata, otherwise, return an error: (Either[CollectionError, Seq[Metadata]])

It turns out that I was doing a lot more work than I needed to be doing. The first thing I did was desugar the for comprehension to a sequenced flatMap and map

getImagesByAuthor(author).flatMap { imagesByAuthor =>
  Future.sequence(imagesByAuthor.map(getImageMetadata)).map { eitherMetadata =>
    if (eitherMetadata.forall(_.isRight))
      Right(eitherMetadata.flatMap(_.toSeq))
    else Left(LookupError(s"Error while looking up image metadata for author: $author"))
  }  
}

What I realized after this desugaring is the “weirdness” of this line:

Future.sequence(imagesByAuthor.map(getImageMetadata))

What I’m effectively doing here is applying an effectful function, e.g. getImageMetadata, with a type signature String => Future[_], where Future is the effect, and applying it to every element of imagesByAuthor. This eventually leads to me having to work with the type: Seq[Future[_]]. Since this is a bit of a hairy type to work with, I used the built-in library function Future.sequence to transform Seq[Future[_]] to Future[Seq[_]].

Traverse

It turns out that this is an incredibly common pattern. Cats provides a library function called traverse that generalizes this “inversion,” with the type signature below

def traverse[F[_]: Applicative, A, B](as: List[A])(f: A => F[B]): F[List[B]]

This was a bunch of gibberish, and I’m going to refer back to the docs all the time, but basically:

• F[_] is a type (a higher-kinded type) that represents a type constructor with a single parameter. Examples include Option[A] or List[T]. The F in these cases would be Option and List.
  • F[_]: Applicative means the type constructor F must be an applicative. I’m not even going to try to explain what that is here (it’s going to be another newsletter, and even then I’ll butcher it).
• A and B are just regular generic types.
• as is a list containing elements of type A
• f is a function that goes from A to F[B]
• the return type of this function is F[List[B]].

I can instantiate traverse like so:

Meaning that I can rewrite what I had before to:

getImagesByAuthor(author).flatMap(_.traverse(getImageMetadata)...

I’m not quite done yet, since the type of the expression above is Future[Seq[Either[CollectionError, Seq[Metadata]]]], which is not what I want.

I need some way to collapse the sequence of Either values inside the Future. What I did was map over the inner value and call combineAll:

getImagesByAuthor(author).flatMap(_.traverse(getImageMetadata).map(_.combineAll))

I am calling .combineAll on the Seq[Either[_]], and I can do this because Seq is a datatype that implements a combine operation. The final result was a refactoring that transformed:

  for {
    imagesByAuthor <- getImagesByAuthor(author)
    eitherMetadata <- Future.sequence(imagesByAuthor.map(getImageMetadata))
  } yield
    if (eitherMetadata.forall(_.isRight)) Right(eitherMetadata.flatMap(_.toSeq))
    else Left(LookupError(s"Error while looking up metadata for author: $author"))

to

getImagesByAuthor(author).flatMap(_.traverse(getImageMetadata).map(_.combineAll))

Pretty cool. I’m not sure if I’ll be using the cats library at work, but it’s definitely something for me to play around with a bit more.

Cat

This was a pretty long newsletter, and the most technical one I’ve written so far. Thanks for reading!