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?

Answer 1

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:

fmap1 f (Foo x g) = Foo (f x) (const (f x))

or:

fmap2 f (Foo x g) = Foo (f x) id

But the problem with fmap1 and fmap2 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.