Sunday, February 15, 2009

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

1 comment:

Tony Morris said...

(<***>) = fmap . fmap

Or for kicks:

(<***>) = fmap `fmap` fmap

Though it doesn't buy you anything ;)