[Haskell-cafe] Natural Transformations and fmap

wren ng thornton wren at freegeek.org
Fri Jan 27 06:30:10 CET 2012

On 1/23/12 10:39 PM, Ryan Ingram wrote:
>      type m :->  n = (forall x. m x ->  n x)
>      class Functor f where fmap :: forall a b. (a ->  b) ->  f a ->  f b
>      -- Functor identity law: fmap id = id
>      -- Functor composition law fmap (f . g) = fmap f . fmap g
> Given Functors m and n, natural transformation f :: m :-> n, and g :: a ->
> b, how can I prove (f . fmap_m g) = (fmap_n g . f)?

That is the defining property of natural transformations. To prove it 
for polymorphic functions in Haskell you'll probably want to leverage 

I assume you don't know category theory, based on other emails in this 
thread. But the definition of a natural transformation is that it is a 
family of morphisms/functions { f_X :: M X -> N X | X an object/type } 
such that for all g :: a -> b we have that f_b . fmap_m g == fmap_n g . f_a

Thus, you can in principle define plenty of natural transformations 
which do not have the type f :: forall X. M X -> N X. The only 
requirement is that the family of morphisms obeys that equation. It's 
nice however that if a function has that type, then it is guaranteed to 
satisfy the equation (so long as it doesn't break the rules by playing 
with strictness or other things that make it so Hask isn't actually a 

Live well,

More information about the Haskell-Cafe mailing list