• Choose a category
• All
• Classic-Fiction

By Root 515 0

think of a list as a box that can be empty or have something inside it, including another box. That box can also be empty or contain something and another box, and so on. So, what else has the properties of being like a box? For one, the Maybe a type. In a way, it’s like a box that can hold nothing (in which case it has the value of Nothing), or it can contain one item (like "HAHA", in which case it has a value of Just "HAHA").

Here’s how Maybe is a functor:

instance Functor Maybe where

fmap f (Just x) = Just (f x)

fmap f Nothing = Nothing

Again, notice how we wrote instance Functor Maybe where instead of instance Functor (Maybe m) where, as we did when we were dealing with YesNo. Functor wants a type constructor that takes one type, and not a concrete type. If you mentally replace the fs with Maybes, fmap acts like a (a -> b) -> Maybe a -> Maybe b for this particular type, which looks okay. But if you replace f with (Maybe m), then it would seem to act like a (a -> b) -> Maybe m a -> Maybe m b, which doesn’t make sense, because Maybe takes just one type parameter.

The fmap implementation is pretty simple. If it’s an empty value of Nothing, then just return a Nothing. If we map over an empty box, we get an empty box. If we map over an empty list, we get an empty list. If it’s not an empty value, but rather a single value packed in a Just, then we apply the function on the contents of the Just:

ghci> fmap (++ " HEY GUYS IM INSIDE THE JUST") (Just "Something serious.")

Just "Something serious. HEY GUYS IM INSIDE THE JUST"

ghci> fmap (++ " HEY GUYS IM INSIDE THE JUST") Nothing

Nothing

ghci> fmap (*2) (Just 200)

Just 400

ghci> fmap (*2) Nothing

Nothing

Trees Are Functors, Too

Another thing that can be mapped over and made an instance of Functor is our Tree a type. It can be thought of as a box (it holds several or no values), and the Tree type constructor takes exactly one type parameter. If you look at fmap as if it were a function made only for Tree, its type signature would look like this: (a -> b) -> Tree a -> Tree b.

We’re going to use recursion on this one. Mapping over an empty tree will produce an empty tree. Mapping over a nonempty tree will produce a tree consisting of our function applied to the root value, and its left and right subtrees will be the previous subtrees, but with our function mapped over them. Here’s the code:

instance Functor Tree where

fmap f EmptyTree = EmptyTree

fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

Now let’s test it:

ghci> fmap (*2) EmptyTree

EmptyTree

ghci> fmap (*4) (foldr treeInsert EmptyTree [5,7,3])

Node 20 (Node 12 EmptyTree EmptyTree) (Node 28 EmptyTree EmptyTree)

Be careful though! If you use the Tree a type to represent a binary search tree, there is no guarantee that it will remain a binary search tree after mapping a function over it. For something to be considered a binary search tree, all the elements to the left of some node must be smaller than the element in the node, and all the elements to the right must be greater. But if you map a function like negate over a binary search tree, the elements to the left of the node suddenly become greater than its element, and your binary search tree becomes just a normal binary tree.

Either a As a Functor

How about Either a b? Can this be made a functor? The Functor type class wants a type constructor that takes only one type parameter, but Either takes two. Hmmm . . . I know, we’ll partially apply Either by feeding it only one parameter, so that it has one free parameter.

Here’s how Either a is a functor in the standard libraries, more specifically in the Control.Monad.Instances module:

instance Functor (Either a) where

fmap f (Right x) = Right (f x)

fmap f (Left x) = Left x

Well well, what do we have here? You can see how Either a was made an instance instead of just Either. That’s because Either a is a type constructor that takes one parameter, whereas Either takes two. If fmap were specifically for Either a, the type signature would be this:

(b -> c) -> Either a b