A functor is a type class that is used for types that can be mapped over.
mapList :: (a -> b) -> [a] -> [b]
mapList g [] = []
mapList g (x:xs) = (g x) : (map g xs)
In the above example, we're mapping the function g
over a list of a
to produce a list of b
.
data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq)
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree g Empty = Empty
mapTree g (Node t1 v t2) = Node (mapTree g t1) (f v) (mapTree g t2)
In this scenario, we're mapping the function g
over a Tree a
to produce a Tree b
.
data Maybe a = Nothing | Just a deriving (Show, Eq)
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe g Nothing = Nothing
mapMaybe g (Just x) -> Just g x
In this scenario, we're mapping the function g
over a Maybe a
to produce a Maybe b
.
So, we'd like to generalize this concept of mapping a function a -> b
over Maybe a
, Tree a
and [a]
- but what do they have in common?
Every type in Haskell has a kind, which is sort of like a type-of-types. Using GHCI, we can figure out what the kind of a type is:
Prelude> :k Int
Int :: *
Prelude> :k Maybe
Maybe :: * -> *
The kind * -> *
is - as per the lecture can be thought of as a "function on types."
Example: The kind of Maybe
is * -> *
. The function on types is awaiting a type of kind *
and will then produce a new type of kind *
. Int
is of kind *
; Maybe Int
is of kind *
, too. We can partially apply these types like we would functions, too.
data Foo a b c = Foo a b c
Prelude> :k Foo
Foo :: * -> * -> * -> *
Prelude> :k Foo Int Char
Foo Int Char :: * -> *
Note that the number of type variables doesn't dictate a type's kind:
data Bar a b = Bar (a b) b
Prelude> :k Bar
Bar :: (* -> *) -> * -> *
Bar is a type that is parameterized by two type variables: a
, which is itself a type which is parameterized by a type b
(of kind * -> *
) and then b
(of kind *
). Thus it's kind is (* -> *) -> * -> *
.
So, what do Tree a
and Just a
and Maybe a
all have in common? They're all of kind * -> *
. We can use this to separate the application of our function a -> b
from the magical context (e.g. Tree a
or Maybe a
or whatever) that holds our a
.
Lo! The Functor
type class:
class Functor f where
fmap :: (a -> b) -> f a -> f b
The Functor
type class can be instantiated by any type f
that is itself parameterized by one other type a
.
It's one required member, fmap
can be described as "give me a mapping function a -> b
and a value of a type which is parameterized by a
and I'll give you back a new value of a type which is parameterized by b
." Let's see one in action:
instance Functor (Tree a) where
fmap f Empty = Empty
fmap f (Node t1 v t2) = Node (fmap f t1) (f v) (fmap f t2)
or for Maybe a
:
instance Functor [a] where
fmap f [] = []
fmap f (x:xs) = (f x) : (fmap f xs)
We've taking our mapTree
and mapMaybe
functions from above and moved them into type class instances of Functor
, which allows us to write code that's functor agnostic, e.g.
valuesToInt :: Functor f => f String -> f Int
valuesToInt fs = fmap read fs
...which can be used with Tree
or Maybe
or List
:
valuesToInt ["1", "200", "12"] // [1, 200, 12]
valuesToInt (Just "123") // Just 123
valuesToInt (Node (Node (Node Empty '30' Empty) '2' Empty) '1' Empty) // (Node (Node (Node Empty 30 Empty) 2 Empty) 1 Empty)
A function of a type a -> b -> c
is a function of kind * -> * -> *
. We know that we can partially apply kinds, which means that for any type of kind * -> * -> *
partially applied to a kind of type *
, we have the kind of Functor
. The implication here is that a partially-applied binary function itself is a unctor`:
instance Functor ((->) e) where
fmap f g = f . g // because f :: a -> b and g :: e -> a, so f . g :: e -> a -> b
And finally:
doubleAndStringify :: Int -> String
doubleAndStringify d = show (d * 2)
valuesToInt doubleAndStringify // Int -> Int
(valuesToInt doubleAndStringify) 23 // 46 :: Int
We encounter functors all over the place:
Stream.of([1, 2, 3]).map(n -> n * 2) // a stream
// RxJs5
Observable<User> oUser = service.getUserById("1234");
Observable<EmailAddress> = oUser.map(x => x.emailAddress); // an observable
// ECMA-262 standard in the 5th edition
[1, 2, 3, 4].map(n => n * 3); // array
// underscore
let f = (n) => n * 4;
let g = (n) => n.toString();
let h = _.compose(g, f); // function composition