I am having trouble writing my own instance of functor for a custom data type (that I cannot change). The data types are defined as:
data Foo a = Baz String (Qux -> Foo a) | Bar a
data Qux = None | Quux String
My problem is with writing a functor for the Foo type. Specifically, I'm not sure how to properly apply my functor function f to the function in the Foo. I was thinking of somehow calling the function in the constructor, but since I don't have any Qux's available for use, I'm stuck.
instance Functor Foo where
fmap f (Bar a) = Bar (f a)
fmap f (Baz s ???) = Baz s (???) -- What goes here?
-- Clearly, something like this doesn't work
-- fmap f (Baz s g) = Baz s (f g)
-- I've also tried something like this, but I'm not sure where to go from there
-- fmap f (Baz s (None -> Bar b)) = Baz s (f b) ???
-- fmap f (Baz s (Quux x -> Bar b)) = Baz s ???
Let's start by completing the left side of this equation. We can write g to bind your function to a variable.
fmap f (Baz s g) = Baz s (???)
Then, we need to fill in the question marks with another function, that takes a Qux and returns a Foo b.
fmap f (Baz s g) = Baz s (\q -> ???)
We can only do one thing with q, which is apply g to it.
fmap f (Baz s g) = Baz s (\q -> g q)
However, this gives us a Foo a, but we need a Foo b! We don't have a function to do that. We do, however, have f, which takes an a and returns a b. If only there were a way to take a -> b and turn it into Foo a -> Foo b... oh wait, there is, it's called fmap!
fmap f (Baz s g) = Baz s (\q -> fmap f (g q))
If you want to write the function in point free notation (https://wiki.haskell.org/Pointfree), you can do this instead.
fmap f (Baz s g) = Baz s (fmap f . g)