Skip to content

Instantly share code, notes, and snippets.

@duplode
Last active January 29, 2022 16:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save duplode/223bf708beba14ced5297ba7f6e33e5f to your computer and use it in GitHub Desktop.
Save duplode/223bf708beba14ced5297ba7f6e33e5f to your computer and use it in GitHub Desktop.
A proof of phantom = fmap f

A proof of phantom = fmap f

phantom is defined as:

phantom :: (Functor f, Contravariant f) => f a -> f b
phantom = contramap (const ()) . fmap (const ())

By parametricity on phantom, we have:

fmap k . phantom = phantom . fmap h

In particular, for k = id, we have (equation #1):

phantom = phantom . fmap h

Now consider:

bar :: (Functor f, Contravariant f) => (a -> x) -> f a -> f a
bar f = contramap f . fmap f

By parametricity:

h' . f = f' . h => fmap h . bar f = bar f' . fmap h

In particular, for f = id, h = id and h' = f', we have (equation #2):

id = bar f'

Next, let's specialise phantom to:

endoPhantom :: (Functor f, Contravariant f) => f a -> f a
endoPhantom = phantom

endoPhantom = contramap (const ()) . fmap (const ()), and, given the specialisation, the two const () are the same here. Therefore:

endoPhantom = bar (const ())

By equation #2:

endoPhantom = id

Finally, by equation #1:

phantom = endoPhantom . fmap h
phantom = fmap h
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment