Functor instance for datatype containing function

Question

I have a datatype defined as

data Foo a = Foo a (a -> a)

The Foo data constructor has two parameter value and function. I need to write Monad and Monad transform instance for this.

I am trying to implement functor instance,

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) (g .(f x))

but I got an error Couldn't match type ‘a’ with ‘b’.

This is correct because g only accepts of type a and f x will convert a->b .So next I rewrote as

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) g

I got the same error "Couldn't match type ‘a’ with ‘b’".

I also tried this

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) (f. g x)

I got Occurs check: cannot construct the infinite type: a ~ b -> a for (g.x)

I am stuck, I know function g only accepts of type a and returns type a. but fmap will convert type a to type b. I think I have to apply fmap over g as well, which I am not able to do.

How do I write the instance for the above datatype?

You can't since the result should be a Foo b (b -> b), but you never transform b to a, hence you can not use the a -> a of the original Foo to construct a function b -> b. Except for the id function (i.e. foo (f x) id), you can not fmap it, but likely that will not hold with the functor laws. — Willem Van Onsem
Thank you. This was given as an assignment for the course I took. I will discuss this question with my tutor. Maybe the question has an typo or incorrect. — Raviteja Sutrave
@WillemVanOnsem Could you please help me understand why do I get "cannot construct the infinite type" for "g x" ? — Raviteja Sutrave
@RavitejuaSutrave: because it expects g x should then have type b -> a, but it has type a, if b -> a is the same type as a then this would result in an infinite recursive type b -> (b -> (b -> ...))). — Willem Van Onsem
Note that you can in fact write a mapping function for this type, just not fmap: it would have to have type signature foomap :: (a -> b) -> (b -> a) -> Foo a -> Foo b. — bradrn

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2021-01-14T21:31:15

Let us take the types into account, we basically need to convert a Foo a to a Foo b, that means we need to find, given a function a -> b, an element of type a and a function with type a -> a, an element of type b and a function of type b -> b.

Especially the last is difficult, since we are only given a function with type a -> b, and not a function with type b -> a, we can not first convert the input to a a, then process it through the orignal function and then map it back to a b.

It is not entirely impossible to make a mapping that satisfies the types, for example:

fmap₁ f (Foo x g) = Foo (f x) (const (f x))

or:

fmap₂ f (Foo x g) = Foo (f x) id

But the problem with fmap₁ and fmap₂ need to satisfy the law:

fmap id = id

In other words fmap id (Foo x g) needs to be equal to Foo x g, now if we use id or const (f x), then id and f x are not always equal to g, at least not if g is a function that can take any form.

If you of course consider Foo x g and Foo x (id x) for example to be equivalent, which might be reasonable in some cases as @leftaroundabout says, then you can implement this as a functor instance.

Functor instance for datatype containing function

1 Answers