Functors, Applicative Functors, and Traversables

This chapter leads us much further into Haskell’s hierarchy of type classes for type constructors: functors, applicative functors, and traversables.

We will introduce the three abstractions in turn as a generalization of particular list-related functionality: mapping, zipping, and mapping with zipping. These list functions provide a good intuition for the mechanics of the generalizations. However, for applicative functors, the notion of effectful computations provides a much better and more important intuition.

Effectful computations are computations that do not only (or necessarily) produce a result. They also do or can do something additional (such as logging, failing, or changing a mutable state) that somehow interacts with the context in which the computation takes place. This is called the (side) effect of the computation.

It is quite paradoxical. On the one hand, Haskell is called a purely functional programming...

Functors

The first constructor type class we will encounter in this chapter is perhaps the simplest of all: Functor. This type class generalizes the higher-order map :: (a -> b) -> ([a] -> [b]).

Recall the definition of map:

Prelude
map :: (a -> b) -> ([a] -> [b])
map f [] = []
map f (x:xs) = f x : map f xs

The second pair of parentheses in the type signature of map can be dropped without changing the meaning. Nevertheless, I like to add them to emphasize that map lifts a function, (a -> b), on elements to a function, ([a] -> [b]), on lists.

The idea is that map transforms the elements of the list without changing the structure of the list itself:

*Main> map show [1,2,3,4]
["1","2","3","4"]

The Functor type class generalizes this idea from lists to other type constructors of the * -> * kind:

Prelude
class Functor f where
  fmap :: (a -> b) -> (f a -> f b)
  (<$...

Applicative functors

Just like the notion of Functor can be understood as a generalization of the map function for lists to other type constructors, the notion of Applicative functors is a generalization of the zip/zipWith functions for lists. However, for the sake of generality, it requires a variant of the zip and zipWith functions that we are already familiar with. Hence, we will explain that setup first before we dive into the general notion of Applicative functors.

A family of zip functions

The standard library provides several zip-like functions to merge lists. The basic one is defined as follows:

Prelude
zip :: [a] -> [b] -> [(a,b)]
zip []     ys     = []
zip xs     []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

This merges the two given lists into a new list by combining the elements at the corresponding positions into a tuple. The new list comes to an end...

Applicative functors and effects

While we have used ZipList and the family of zip functions as our initial intuition for the notion of applicative functors, there is a different notion that is helpful to understand most Applicative instances: (computational) effects. The idea is that, whereas A denotes a readily available value, F A denotes a computation that yields a value of A. Depending on the type of computation, F, other relevant effects may happen during the computation. For example, the computation may fail for some reason, and thus not produce a value at all. We will explore this and several other other possible effects through different Applicative instances.

Failing computations with Maybe

Failing computations may or may not yield a result. We have already modeled these using the Maybe type constructor, where Just x denotes a successful outcome with a result, x, and Nothing denotes failure to produce a result.

This type of constructor has the following instance:

...

Traversables

Recall that the functorial map (fmap) lifts pure functions of the a -> b type to functions on collections of the t a -> t b type. The Traversable type class generalizes this to effectful functions, a -> f b, with f as an applicative functor.

First, let’s compare the two for lists (viewed as a collection, not as an effect):

fmap :: (a -> b) -> ([a] -> [b])
fmap f []     = []
fmap f (x:xs) = f x : fmap f xs
traverse :: Applicative f => (a -> f b) -> ([a] -> f [b])
traverse f []     = pure []
traverse f (x:xs) = pure (:) <*> f x <*> traverse f xs

As we can see, the structure is quite similar. The main difference is that traverse uses the application, (<*>), of applicative functors, and lifts the list constructors with pure.

The Traversable class

The type class declaration looks as follows:

Prelude
class (Functor t, Foldable t) => Traversable t where...

Summary

In this chapter, we expanded our repertoire of type constructor classes. We studied a generalization of the list map function to another type of constructor, which is known as a functor. Next, we introduced a generalization of zipping, which is particularly useful for modeling a large range of different kinds of computational effects: applicative functors. Finally, we covered a generalization of mapping with pure functions to mapping with effectful functions, which is supported by the so-called traversable functors.

Chapter 11, Monads, continues with modeling effectful computations using type constructor classes. It introduces perhaps the main concept that Haskell is famous for: monads. These monads characterize a particular subset of applicative functors that are particularly flexible and general for effectful computations.

Questions

Here are some questions and their answers so that you can test your knowledge of this chapter:

1. What is a functor?
2. What is an applicative functor?
3. What effects can I model with applicative functors?
4. What is a traversable functor?

Further reading

To learn more about the topics that were covered in this chapter, take a look at the following resources:

• The Control.Applicative library documentation:

  https://hackage.haskell.org/package/base-4.18.1.0/docs/Control-Applicative.html

• The Data.Traversable library documentation:

  https://hackage.haskell.org/package/base-4.18.1.0/docs/Data-Traversable.html

Answers

1. A functor is a type constructor, f, with an instance of the Functor type class:

   class Functor f where
     fmap :: (a -> b) -> (f a -> f b)
     (<$) :: b -> (f a -> f b)
     x <$ t = fmap (\_ -> x) t

   This is subject to the identity and fusion laws:

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

2. An applicative functor, f, is a functor with an instance of the Applicative type class:

   class Functor f => Applicative f where
     pure :: a -> f a
     (<*>) :: f (a -> b) -> f a -> f b
     fs <*> xs = liftA2 ($) fs xs
     liftA2 :: (a -> b -> c) -> f a -> f b -> f c
     liftA2 f xs ys = fmap f xs <*> ys
     (*>) :: f a -> f b -> f b
     xs *> ys = liftA2 (\_ y -> y) xs ys
     (<*) :: f a -> f b -> f a
     xs <* ys = liftA2 (\x _ -> x) xs ys

   This is subject to four laws:

   pure id <*> v...