Brent Yorgey's Typeclassopedia gives the following exercise:
Give an example of a type of kind
* -> *
which cannot be made an instance ofFunctor
(without usingundefined
).
Please tell me what "cannot be made an instance of Functor
" means.
Also, I'd appreciate an example, but perhaps as a spoiler so that you can, please, guide me to the answer.
The functor laws express that a translation of functions preserves the structure of how the functions compose, in addition to preserving the structure of the containers. Mapping a set doesn't preserve those structures, and that's the reason that sets aren't functors.
An intuitive example of something that's a Functor but not an Applicative is a tagged value, where you have a value that's associated with some arbitrary "tag". This is a functor - given a function f and a tagged value ("tag1", v), you can map over it to get the result ("tag1", f(v)).
Functor in Haskell is a typeclass that provides two methods – fmap and (<$) – for structure-preserving transformations. To implement a Functor instance for a data type, you need to provide a type-specific implementation of fmap – the function we already covered.
Functor in Haskell is a kind of functional representation of different Types which can be mapped over. It is a high level concept of implementing polymorphism. According to Haskell developers, all the Types such as List, Map, Tree, etc. are the instance of the Haskell Functor.
A type t
of kind * -> *
can be made an instance of Functor
if and only if it is possible to implement a law-abiding instance of the Functor
class for it. So that means you have to implement the Functor
class, and your fmap
has to obey the Functor
laws:
fmap id x == x
fmap f (fmap g x) == fmap (f . g) x
So basically, to solve this, you have to name some type of your choice and prove that there's no lawful implementation of fmap
for it.
Let's start with a non-example, to set the tone. (->) :: * -> * -> *
is the function type constructor, as seen in function types like String -> Int :: *
. In Haskell, you can partially apply type constructors, so you can have types like (->) r :: * -> *
. This type is a Functor
:
instance Functor ((->) r) where
fmap f g = f . g
Intuitively, the Functor
instance here allows you to apply f :: a -> b
to the return value of a function g :: r -> a
"before" (so to speak) you apply g
to some x :: r
. So for example, if this is the function that returns the length of its argument:
length :: [a] -> Int
...then this is the function that returns twice the length of its argument:
twiceTheLength :: [a] -> Int
twiceTheLength = fmap (*2) length
Useful fact: the Reader
monad is just a newtype
for (->)
:
newtype Reader r a = Reader { runReader :: r -> a }
instance Functor (Reader r) where
fmap f (Reader g) = Reader (f . g)
instance Applicative (Reader r) where
pure a = Reader (const a)
Reader f <*> Reader a = Reader $ \r -> f r (a r)
instance Monad (Reader r) where
return = pure
Reader f >>= g = Reader $ \r -> runReader g (f r) r
Now that we have that non-example out of the way, here's a type that can't be made into a Functor
:
type Redaer a r = Redaer { runRedaer :: r -> a }
-- Not gonna work!
instance Functor (Redaer a) where
fmap f (Redaer g) = ...
Yep, all I did is spell the name backwards, and more importantly, flip the order of the type parameters. I'll let you try and figure out why this type can't be made an instance of Functor
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With