Applicative Functors in Haskell

Introduction

As a follow up to my previous post on Functors, it’s a natural progression for me to do a post on the more advanced version, the Applicative Functor. In a normal functor, you’ll map a function over a functor and applicative functor is a reverse view of this where it’ll allow you to map many functor values over a single function.

What is an Applicative Functor?

At the code level, an Applicative Functor is any type that is in instance of the Applicative typeclass. At a concept level, the Applicative Functor has not only the values in “a context” but also the function that we’ll apply is in a context. This differs from just a normal Functor where it’s only the value that’s wrapped in a context. An Applicative Functor has 2 functions that require implementation. pure and <*>. This typeclass and functions are defined as follows.

class (Functor f) => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

The definition for pure on Hoogle suggests that it will

Lift a value

“Lifting” is very well described in articles all over the web. Here’s the Haskell Wiki’s article on Lifting. pure takes in a value and returns an applicative value around that value. It’s actually quite a simple definition when you read it. The other function defined here is <*>. The definition for <*> on Hoolgle suggests that it will perform

Sequential application

The definition of sequential application here can be expanded such that <*> takes a function (a -> b) wrapped up in a functor f and another functor value f a. It’ll extract the function from the first parameter (a -> b), map it over the functor value f a to produce a result f b. The concept is very similar to what we’ve seen before in mapping scenarios, it’s just that we “map” with different “things”. Today we’re mapping with functor values over a function.

pure

Here’s some examples of pure in action. You’ll see that when we’re casting to a type, we receive the appropriate value back

> pure "Hey" :: Maybe String
Just "Hey"
> pure "Should be in a List" :: [String]
["Should be in a List"]

You can see here that the value is “lifted” by pure into the container (in this case either a Maybe or a List).

<*>

For the next set of examples, I’ll show you some usages of <*>. You’ll need to keep in the front of your mind that all functions on the left hand side are applied to all values on the right hand side, so we end up with a Cartesian effect.

> [sin, cos, tan] <*> [pi, pi, pi]
[1.2246467991473532e-16,1.2246467991473532e-16,1.2246467991473532e-16,-1.0,-1.0,-1.0,-1.2246467991473532e-16,-1.2246467991473532e-16,-1.2246467991473532e-16]

The <*> function is left associable, so when you start chaining calls together it’s the leftmost that is evaluated first.

> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

(which is really)
[1+3,1+4,2+3,2+4,1*3,1*4,2*3,2*4]

Applicative Style

You can see how using this “applicative style” in code can often be swapped 1-for-1 with list comprehensions as you achieve the same permuted or Cartesian effect. Take this for example.

> [salutation ++ name | salutation <- ["Hello ", "Goodbye ", "Yo! "], name <- ["John", "Mary", "Anne"]]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

> (++) <$> ["Hello ", "GoodBye ", "Yo! "] <*> ["John", "Mary", "Anne"]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

You can see that when dealing with lists, the following is true:

pure f <*>; xs == fmap f xs

In this context, pure f is putting f into a list. [f] <*> xs just applies each function in the left list to the right. Another implementation of the Applicative Functor that doesn’t follow the same notion of a List is its use with IO. The idea of the applicative functor still holds, but when dealing with IO its the actions that are operated on. This can be thought of in the same way as sequencing and mapping in one.

ZipList

Another type that is an instance of Applicative is the ZipList. The ZipList type is defined as follows.

instance Applicative ZipList where
  pure x = ZipList (repeat x)
  ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

When we use applicative style on a normal list, we end up with a Cartesian product of the two lists involved. A ZipList differs here by operating on indicies in either list that are the same. Index [0] on the left gets applied to Index [0] on the right. Index [1] on the left gets applied to Index [1] on the right, and so on.

Applicative Functor Laws

Finally, there are a few laws that applicative functors must abide by, they are as follows.

• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <> pure y = pure ($ y) <> u

Applying applicative functors for yourself

This has been a very difficult topic that I’ve burnt some time on as late. There are plenty of examples of how this knowledge has been applied for a List or Maybe, but I’ve struggled to apply this to a type of my own. So far though, I’ve come across this article on Applicative Functors on the Hakell Wiki and most notably this sentence:

Anytime you feel the need to define different higher order functions to accommodate for function-arguments with a different number of arguments, think about how defining a proper instance of Applicative can make your life easier.

That to me makes sense. So, if you have a function that operates on a particular type and you’d like to apply that function to “n” arguments - you’d normally create an fmap clone that would cater for that many arguments. Using an applicative functor, the re-creation of the fmap instance goes away as your higher-order function can expect any number of arguments. Because of this, the following is true.

fmap2 f a b = f `fmap` a <*> b
fmap3 f a b c = f `fmap` a <*> b <*> c
fmap4 f a b c d = f `fmap` a <*> b <*> c <*> d

That’s it for today’s post. I hope to update this post with some more examples and information as I discover it!

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.