Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Make Data Type of Kind * -> * That's Not a Functor

Brent Yorgey's Typeclassopedia gives the following exercise:

Give an example of a type of kind * -> * which cannot be made an instance of Functor (without using undefined).

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.

like image 849
Kevin Meredith Avatar asked Nov 18 '14 02:11

Kevin Meredith


People also ask

Why is set not a functor?

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.

What is a functor but not applicative?

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)).

Is functor a type class?

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.

What is a functor in Haskell?

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.


1 Answers

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.

like image 187
Luis Casillas Avatar answered Oct 14 '22 06:10

Luis Casillas