Fun with functors

I have been slowly working through some more Haskell with help from Tony.

1. Quickly worked through the previous stuff we did to refresh my memory.


2. Consider a simplified version of the Eq type class.

   class Eq a where 
     (==) :: a -> a -> Bool

   The type variable a is polymorphic over types. Now consider the Functor type class.

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

   Here we have an example of higher-order polymorphism, e.g. f a, f b. The type variables a and b are polymorphic over types as before, but f is polymorphic over type constructors. Note that f has kind * -> * as it is applied to a single type variable in both cases.


3. The Maybe type constructor has kind * -> *. We have effectively already written the Functor implementation, i.e. the mmap function in the previous work.

   class Functor' f where
     (<$>) :: (a -> b) -> f a -> f b
   
   instance Functor' Maybe where
     (<$>) = mmap



4. Observe that -> is a type constructor with kind * -> * -> *. Given two types a and b, a->b is the type of functions mapping elements of type a to elements of type b.
   
   We can't write a Functor instance for the -> type constructor as their kinds are different. However we can partially apply a polymorphic type, lets call it t which gives ((->) t) and has kind * -> *.


5. Exercise: write an instance of Functor for functions:

   instance Functor' ((->) t) where
     (<$>) = error "todo"

   Looks a little nasty when you first see it. Its a bit easier if you write out the type signature with the type constructor applied.

   <$> :: (a -> b) -> ((->) t a) -> ((->) t b)

   It is more obvious in infix form.

   <$> :: (a -> b) -> (t -> a) -> (t -> b)

   Now it is fairly easy to come up with an implementation.


6. Exercise: just for fun, write a Monad instance:

   class (Functor' m) => Monad' m where
     flatMap :: (a -> m b) -> m a -> m b
     pure    :: a -> m a
   
   instance Monad' ((->) t) where
     flatMap = error "todo"
     pure    = error "todo"

   Again writing out the type signatures helps.


7. Note the laws that all Functor instances should satisfy.

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

   The combination of the Functor type class and these laws define a particular concept/pattern. Intuitively function composition and the traditional map function seem like very different things, yet they are both instances of this abstraction.


8. Exercise: write an implementation for:

   (<***>) :: (Functor f, Functor g) => (a -> b) -> g (f a) -> g (f b)

   It took me a while, with help, so the answer is at the bottom of the post.

This is all well and good, but what use is it? Here are two examples of using the <***> function.

Example 1

data Connection = Connection

newtype Conn a = Conn {
  conn :: Connection -> a
}

instance Functor Conn where
  k `fmap` Conn z = Conn (k . z)

data ResultSet = ResultSet
data Person = Person

f :: ResultSet -> Person
f = undefined

executeQuery :: String -> Conn ResultSet
executeQuery = undefined

k :: String -> Conn Person
k = f <***> executeQuery

Example 2

g :: Maybe [Bool] -> Maybe [String]
g = (<***>) show

Useful references.

1. A Gentle Introduction to Haskell: 2 Values, Types, and Other Goodies


2. Functional Programming with Overloading and Higher-Order Polymorphism

Answer for 7.

(<***>) :: (Functor f, Functor g) => (a -> b) -> g (f a) -> g (f b)
f <***> g = (f `fmap`) `fmap` g

Or in point free form.

(<***>) = fmap . fmap