Functors in Haskell

Introduction

In a previous post, I had lightly grazed the surface of the topic of Functors in Haskell and I thought it was time to come back and be a little more comprehensive about it. Without further ado, let’s talk about Functors.

What is a Functor?

At the code level, a Functor is any type that is an instance of the Functor typeclass. At a concept level, a Functor is something that can be mapped over. As soon as anyone says something like this to me I immediately start thinking of any enumerated type (array, list, vector, etc) and this is right.

A Functor only needs to implement 1 function, fmap. How this looks in Haskell is as follows.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Reading this gets to be a mouthful, but bear with me. This definition says: “for my first parameter, I want a function that takes an a type and returns a b; for my second parameter, I want an a value wrapped by this functor and I will return you a b value wrapped by this functor”. I’ve tried to place emphasis on a’s and b’s in that previous sentence, otherwise it reads like rather difficult english. Applying this knowledge to a living-breathing example, I’ll show you the Maybe type.

instance Functor Maybe where
  fmap f (Just x) = Just (f x)
  fmap _ Nothing  = Nothing

Looking at this we can see that when a Just value comes through, it’s the value (wrapped in the Just) that has the function applied to it. When nothing comes through, we don’t care for the function - we know that the return is going to be Nothing. The important thing to note here is that it’s the value (wrapped in the Just) that’s being operated on. Seeing this in action always helps an explanation.

ghci> fmap (replicate 3) (Just 4)
Just [4, 4, 4]

The way that I read this is: “A function” fmap “that takes a function” (replicate 3) “and a functor value” (Just 4) “that then maps that function” (replicate 3) “over the inner value” (4) “which gets wrapped up in the functor” (Just). This is the best way that I could think of to structure this sentence. It makes sense to me, I hope it helps you also. Again, the important thing to remember is that it’s the inner-value that’s getting processed which is why we ended up with Just [4, 4, 4] rather than [Just 4, Just 4, Just 4]. Finally, when you’re implementing functors of your own there are laws that must be met.

Law #1

Mapping the id function over any functor value should produce the functor value that we supplied.

fmap id = id

Law #2

Mapping two composed functions over a functor value should be the same as functionally composing those two functions.

fmap (f . g) = fmap f . fmap g

This second law makes sense once you think about performing fmap over a function, as it’s just the same as function composition.

fmap (*15) (-2) == (*15) . (-2)

This post should arm you sufficiently to start inflicting your own Functors on the world.

Uniform Initialization with C++11

Initialization of variables types has received a face lift with the new version of the C++ standard. Previously trying to initialize a populated list was impossible and you were left writing helper functions to transform array values into other container types, or worse you’d end up with code that looked like this.

vector<int> i;

// populate the vector
i.push_back(1);
i.push_back(2);
i.push_back(3);
i.push_back(4);

C++11 includes a feature called “Uniform Initialization” which aims to solve this problem. The above code now turns into this.

vector<int> i {1, 2, 3, 4};

Much better. This isn’t where the convenience ends though. Take the following example. Because the person class defines a constructor taking in first_name, last_name and age we are able to use uniform initialization to setup these variables.

// declare the person class
class person {
  public:
    person(void) = default;
    person(const string& fn, const string &ln, const int a) 
      : first_name(fn), last_name(ln), age(a) { }
    virtual ~person(void) = default;

  private:
    string first_name, last_name;
    int age;
};

// initialize a person
person p { "John", "Smith", 25 };

// initialize a vector of people
vector<person> people { {"Mary", "Brown", 21},
                        {"Joe", "Jones", 35},
                        p,
                        {"Sally", "Green", 32} };

The same syntax works with any of the enumerated containers. Using the person class from above, we can make a map of employee records by doing the following.

map<int, person> employees {
  {1, {"Mary", "Brown", 21}},
  {2, {"Joe", "Jones", 35}},
  {3, {"John", "Smith", 25}},
  {4, {"Sally", "Green", 32}}
};

You can see how this syntax makes the initialization process a much more pleasant experience in C++ now. That’s all for this one.

Rvalue references in C++11

This is the biggest change (shift anyway) in C++’s thinking with the new standard. This preview of Rvalue references probably isn’t pitched at the novice and a bit of prior knowledge is assumed. You’ll want to know the differences between an Lvalue and an Rvalue, you’ll also want to understand how temporary objects work but most importantly why they’re evil in some scenarios. With all of that information under our belt, I can see that the Rvalue reference came to fruition to resolve the copy problem. Returning a temporary object from a function that you’d use in your program would cause an expensive copy operation, now this is is resolved with move semantics. Rather than that expensive copy operation, the value that’s returned is pilfered to the calling code and the temporary object is left empty, ergo a move occurs. An Rvalue reference is defined in code like so.

person&& p = get_temp_person();

The double ampersand && tells us that it’s an Rvalue reference. We can give our own classes the ability to “move” a value by introducing a move constructor and operator like so.

class person {                       
   public:                           
    person(person&& p);            
                                     
    person& operator=(person&& p);
                                     
  public:                           
    string first_name,             
           middle_name,            
           last_name;              
};                                   

The STL containers have all been optimised to use move syntax, so you’ll pick up this copy-free functionality on the way.

nullptr in C++11

It happened! It finally happened! NULL has a real identity within the language. Forever I’d used the notion of NULL in my C & C++ to really mean 0 (zero) under the covers.

#define NULL 0

Of course, I’d never defined it myself. It was always done for me in one of the many include files drawn into my program. One of the problems with this particular define is for overloaded methods. If you were to pass NULL in its defined state above, you’d be guessing as to which overload is called.

void useptr(float* p) { /*...*/ }
void useptr(char* p) { /*...*/ }

// float* or char*??
useptr(NULL);

Well, now we have nullptr in C++11. nullptr is castable to any pointer type.

int* p = nullptr;
char* str = nullptr;
person* someone = nullptr;

The castability also covers off on boolean expressions, so the following if-trees will still work.

if (!p) {
  cout << "p was null!";
}

Finally, nullptr is of type nullptr_t. If you’re going to find it of use to you to guarantee that a null pointer is going to be passed into a method, you could type your method using the type nullptr_t.

Null now has a home.

Enum Classes in C++11

Enums in C/C++ have traditionally just been a pretty face for an integer value. That hasn’t changed so much, but a new breed of enumeration has been added with C++11: enter the enum class. Enum classes have been introduced as a “strongly typed” enum. This gives you type safety in your enums so that you don’t perform comparisons between enum types and if you do you’ll need to explicitly define how the two should be compared. The other major benefit is improved scoping. Enum class values must always mention the enumeration that they belong to in order to be used. Here’s an example of an enum class.

enum class Suit { HEART, DIAMOND, CLUB, SPADE };

Immediately the only difference that you’ll see here is the addition of the word class. You can still explicitly type and value your enumerations. Here’s the same example above only written more verbosely.

enum class Suit : unsigned char {
  HEART = 0, DIAMOND = 1, CLUB = 2, SPADE = 3
};

An example usage of these enum classes goes as follows.

void show(const Suit s) {
  switch (s) {
    case Suit::HEART:
      cout << "hearts";
      break;

    case Suit::DIAMOND:
      cout << "diamonds";
      break;

    case Suit::CLUB:
      cout << "clubs";
      break;

    case Suit::SPADE:
      cout << "spades";
      break;
  }
}

Well, there you have it. A brief tour of enum classes in C++11.