return



This is an article explaining the concept of functor to programmers who are interested in Haskell but not sure how to get started on those abstract ideas.

Many articles introduce functional programming with examples of maping, filtering and reduceing arrays, but it feels like it is not very useful except from array manipulation. This post focus on the map concept and try to explain how is it useful in other ways.

(This is the 10th post for Haskell Advent Calendar 2017)


Array

Lets start with the simplest form, Array. Mapping an array means to apply a function to each of the element in the array. In Javascript, you can write something like this:

[1, 2, 3, 4].map(x => x * 2) // [2, 4, 6 ,8]

With this kind of result, you may consider map to be a convenient function that performs loop internally, and that is a kind of specialised loop.

Optional

In some languages, there is a concept called optional type, or Maybe. It wraps around a value and force users to wrap before using the value. I am using Swift as an example.

// It is possible that 9 is not in the array
// so the return type is an optional integer
let index: Optional<Int> = [1,2,3].index(of: 9)

// Explicitly do the null check
let message: Optional<String> = nil
if let i = index {
  message = "The index is \(i)"
}

Array and Optional does not seem to be related at all, but if you think deeper, Optional can be treated as a special form of Array. It is like an array that can only contain maximum one element. If you find it difficult to imagine, consider this:

[].map { x in x + 1 }   // [], this is like a `Optional.none`
[1].map { x in x + 1 }  // [2], this is like a `Optional.some(1)`

If you can wrap your head around this model, then maping an Optional value makes a lot of sense. The above code can be replaced by a much cleaner version:

let index: Optional<Int> = [1,2,3].index(of: 9)
let message = index.map { i in "The index is \(i)" }

Mapping for optional is like a specialised if, it only transforms value if there is one.

Observable

Lets go back to the Array type, and tweak it a bit. What if values are not ready from the beginning, but are prepared in an asynchronous way? That is what Rx's Observable is about, in some frameworks they call it Stream.

Observable.of(1,2,3).map(x => x + 1);
// same as Observable.of(2,3,4)

Mapping an observable is very similar to mapping an array, but it is more flexible because it can model asynchronous data like this:

// A stream of event
Observable
  .fromEvent(document.querySelector('button'), 'click')
  .map(event => event.target.value) // transforming to a stream of value

// Or creating a stream for http request
Rx.DOM.ajax('http://example.com')
  .map(data => data.status)

Mapping an observable feels like wrapping around another obserable. The new observable emits a value when the old one has a value. The new value is calculated from the old value with the mapping function.

Promise

Just like how Optional can be considered as a special form of Array, we can also make a special form of observable, which can only gives maximum one value. That is usually called a Promise, and is used like this:

const fetchUsername = () =>
  fetchUser().then(user => user.username);

Just like Observable, when you have the Promise, you are not sure when will the value comes, or it may not even come at all, but unlike Observable, promise can only provide one value, you cannot have a promise that resolve multiple times. You may have noticed, the above usage of then is just like what we are doing with Observable's map. As long as you are not returning a Promise inside then, the function then actually behave exactly like map.


How are they similar?

So there we go, 4 types, Array, Optional, Observable and Promise. You don't hear people say "a Promise is like an Array", but there is one thing in common as demonstrated, they are all "mappable". What exactly makes them "mappable"? map is like a loop for Array, but that's not true for Optional and Promise. map is like a if for Optional, but that's not true for Observable. map is like an event handler for Promise and Observable, but that's not true for Array.

The first similarity you might realise is, all the types above are types that require a type parameter (it's usually called "generic"). For example in Swift you cannot have a value for just Array, it has to be something like Array<Int>, or Array<String>, there has to be another type associated before you can have a value. In dynamic languages like JS, you don't have that kind of notation, but the concept is still the same, you cannot have just a promise, it has to be something like Promise of String.

Second similarity, speaking of that "associated type", you may also realise the map function always transform the value "inside". For example if you have an Array<Int>, the map function has to transform the value with a function like Int -> Something. If you have a Promise of String, the function inside then has to accept String as an argument.

Third similarity, the result after mapping is always associated when the type of the output type of the mapping function. For example, after mapping an Array<Int> with function of type Int -> String, the result has to be Array<String>. After mapping a Promise of String with a function String -> Boolean, the result has to be a Promise of Boolean. There is no exception.

The above behaviours are what I'd consider making a type a "mappable". It is not about how it is implemented, but how is the value transformed. In functional languages, another name is used instead of "mappable", we call it Functor, and here is its definition:

class Functor f where
  map :: forall a b. (a -> b) -> f a -> f b

(Those arrows might make things look difficult, that's just currying, don't worry.)

The above code defines a function, that

  • For any type a and b,
  • It takes a function that receive an a and returns a b,
  • It also takes a functor of a,
  • It returns a functor of b.

If that's too abstract, try substituting the type variables with actual types, e.g. when a is String and b is Int, map for Array will be (String -> Int) -> Array String -> Array Int.

To make a type a Functor, it also has to follow some laws

  • Identity: map id = id

    • Translation: Mapping something with an identity function should returns an output same as the input. Example:

      arr.map(x => x) === arr
      
  • Composition: map (f <<< g) = map f <<< map g

    • Mapping something with function like this:

      arr.map(x => x + 1).map(x => x * 2)
      

      Should be identical to the following code:

      arr.map(x => (x + 1) * 2)
      

It is ok not to remember the laws, you don't need to recall them when you use map anyway. Just use it as a reference when you are confused.

With the concept of Functor, you can write more reusable code that wasn't possible. For example you may create a function that takes a functor, without caring is it an Array, an Observable, an Optional or a Promise, or even a Tree, a Dictionary, a Function, or your own data structure. The function just maps things as usual without bounded by the underlying implementation detail. It also makes code more flexible because it is making very few assumption on the input type. I once had a function that might fails, it returned a Maybe Int, but I changed my mind that there has to be an error message in case of error. Maybe is not capable of that, so I changed it to Either String Int. Later on, I find out the operation is asynchronous, so I changed the type to Aff eff Int. Even the type has changed a lot, the codes that I have to modify is surprising few, most of them are operating with type classes (e.g. Functor) already, everything is ready for change at the first place.

Apart from Functor, there are many type classes that model different abstract concepts in functional programming. They may looks scary in the beginning, but they are easier than you think and can become really useful later. I recommend learning concepts like Applicative, Monad, Comonad, Traversable. In case of getting stuck, it is always good to look at different types that belong to that type class and look for their similarity. Promise is also a good point to start thinking because it is a well-known concept and it's a Functor, Bifunctor, Alt, Applicative (I never see anyone using it as an applicative, but it is possible), Monad, MonadThrow, MonadError and many more.