Exploring an Implementation of Functors

Functors are a very common word encountered within functional programming circles, but the concept extends far beyond. At its core Functors are about translating between types. Wikipedia will define Functors as a function that maps from one type to another, however in most functional languages Functors endup being structures that can be mapped over. In the remainder of this post we’ll be defining an interface for a Functor and how it ties into everyday programming.

Defining a Functor

Thinking back to the basic definitions of functor, we get the impression that they can be functions translating between types. Some exaples of this are:

• Converting Int to String
• Converting String to Int
• Converting a class to JSON
• Converting JSON to some class
• Converting from a String to another String with another value

as functions these may look like:

String toString(int value) => new String.fromCharCode(value);
int toString(String value) => value.charCode;
// ...etc

Feeding the basic values into our functions works wondefully, but often times our values are nested within some object(or context) and given we have built these useful basic functions for transforming our data, it would be useful to be able to reuse such functions. This is where the second definition of Functors starts to show its head.

Suppose we’re making an application that makes some HTTP call and recieves a response object with a value. It’s possible we’d want to do something like deserialize that response body while maintaining the reset of the response context. The response context being response code, headers, etc.

We could go about writing something like:

// Pseudo Code:
Response<JSON> response = await server.request("https://btellez.com");
BlogPost body = jsonToBlogPost(response.body);
Response<BlogPost> updatedResponse = response.withNewBody(body);

While there is nothing wrong about this, there is a pattern here that applies to so many other types in programming: getting, transforming, and setting a value. It would be really nice if we had a function on Response that could transform it’s body value given a function.

Response<JSON> response = await server.request("https://btellez.com");
Response<BlogPost> updatedResponse = response.map(jsonToBlogPost);

How might we be able to generalize this behaviour for built in types and custom types?

Defining Functor Behaviour

If we think about the behaviour above we really are trying to define a map function for some type. We could define stand alone functors that know how to map over artbitrary objects. Consider the following interface:

abstract class Functor<F> {
  F map<A, B>(F target, B f(A _));
}

We could then build a Functor for any type…

class ResponseBodyFunctor extends Functor<Response> {
  Response<B> map<A, B>map(Response<A> input, B f(A _)) {
    input.withNewBody(f(input.body));
  }
}

We could then use this Functor…

  Response<JSON> response = await server.request("https://btellez.com");
  Response<BlogPost> updatedResponse = new ResponseBodyFunctor.map(response, jsonToBlogPost);

Admittedly, the amount of code to do this is much more than what we would have written had we just used our original code. However the idea here is that we can write code that accepts Functor instances and is able to compose them and act on arbitrary types that can be mapped over.

For example the following function is a generic toString that can use any Functor Instance to map over the values of a data structure.

A toStringWithTime(Functor<A> f, A) {
  val time = "1:00pm"; // It's 5:00pm somewhere!?
  return f.map(A, (value) => "$time: $value");
}

One very common place functors are often recognized is in lists. List are things that can be mapped over and transformed. Below is an example of what functor may look like when applied to lists:

class ListFunctor extends Functor<List<A>> {
  List<B> map<A, B>map(List<A> input, B f(A _)) {
    List.of(input.map(f)); // Converting from Stream back to List;
  }
}

Given this list functor, we could reuse our toStringWithTime method to convert all values of the list to string tagged with our time.

This method of defining a Functor separate of the data structure is useful, but cumbersome. This method allows us to extend the behaviour to all data types. However, if we wanted to implement this behaviour for our own custom types, we could defined a similar interface to remove some of the overhead of defining a separate Functor instance.

Functor Operations in Custom Types

We are going to call this new interface FunctorOperations, and it’s going to define a map method also similar to Functor however since this interface is something our source class implements we can simplify the argument list a bit.

abstract class FunctorOperations<F, A> {
  // Function that accepts a function which transforms the contents
  F map<B>(B f(A _)); 
}

Say we are defining our own HTTP library with a similar Response class, we could bake in the functor behaviour by extending FunctorOperations and defining map.

class Response<A> extends FunctorOperations<Response, A> {
  A body;
  Response(this.body);
  Response<B> map<B>(B f(A _)) => new Response(f(body));
}

This method is much more streamlined, but it requires us to be able to modify or extend classes we want to be able to map over in the same predicable manner.

Functor Laws

There are two properties about functors often referred to as Functor Laws.

First, functors must preserve identity. This means that if functors are given an identity function they must return the same value.

A identity<A>(A a) = a;

// The following must hold:
response.map(identity) == response;

Second, functors must preserve composition. This means that composed functions must be equivalent to composing of the functor.

String toString(A a) = "$a";
List<A> toList(A a) = List<A>(a);

// The following must hold:
response.map(toString).map(toList) == response.map((value) => toList(toString(x)));

The reason we may want to assert that these laws hold for functors is more about being able to provide realiable mechanism for mapping over types everywhere. it’s about defining reliable behaviours.

Conclusion

Functor can be viewed as the standardized method for mapping over types. While it’s use is not required in a language like Dart, I feel it’s a good exercise to see how one might go about implementing particular functional paradigms in a language which does not support them out of the box or has them baked into it’s standard library.

Additional Resources

• Wikipedia: Functor
• Dartz: Functional Programming Library for Dart