haskell - How can I show that traverse interacts sensibly with fmap? -

it seems intuitively obvious following law should hold:

traverse f . fmap g = traverse (f . g) 

the traversable law seems apply directly is

fmap g = runidentity . traverse (identity . g) 

that changes problem to

traverse f . runidentity . traverse (identity . g) 

the law seems have vaguely right shape apply naturality law. that, however, applicative transformations, , don't see of around.

unless i'm missing something, thing left parametricity proof, , i've not yet gotten clue how write those.

note proof isn't necessary, result in question indeed free theorem. see reid barton's answer.

i believe do:

traverse f . fmap g -- lhs 

by fmap/traverse law,

traverse f . runidentity . traverse (identity . g) 

since fmap identity id,

runidentity . fmap (traverse f) . traverse (identity . g) 

the compose law offers way collapse 2 traversals one, must first introduce compose using getcompose . compose = id.

runidentity . getcompose . compose . fmap (traverse f) . traverse (identity . g) -- composition law: runidentity . getcompose . traverse (compose . fmap f . identity . g) 

again using identity fmap,

runidentity . getcompose . traverse (compose . identity . f . g) 

compose . identity applicative transformation, naturality,

runidentity . getcompose . compose . identity . traverse (f . g) 

collapsing inverses,

traverse (f . g) -- rhs 

invoked laws , corollaries, sake of completeness:

-- composition: traverse (compose . fmap g . f) = compose . fmap (traverse g) . traverse f -- naturality: t . traverse f = traverse (t . f) -- every applicative transformation t -- `fmap` traversal: fmap g = runidentity . traverse (identity . g) 

the latter fact follows identity law, traverse identity = identity, plus uniqueness of fmap.