[Haskell-cafe] lawless instances of Functor
ajb at spamcop.net
ajb at spamcop.net
Mon Jan 4 21:47:23 EST 2010
G'day all.
Quoting Derek Elkins <derek.a.elkins at gmail.com>:
> Ignoring bottoms the free theorem for fmap can be written:
>
> If h . p = q . g then fmap h . fmap p = fmap q . fmap g
> Setting p = id gives
> h . id = h = q . g && fmap h . fmap id = fmap q . fmap g
> Using fmap id = id and h = q . g we get,
> fmap h . fmap id = fmap h . id = fmap h = fmap (q . g) = fmap q . fmap g
Dan Piponi points out:
> When I play with http://haskell.as9x.info/ft.html I get examples that
> look more like:
>
> If fmap' has the same signature as the usual fmap for a type
> and h . p = q . g
> then fmap h . fmap' p = fmap' q . fmap g
>
> From which it follows that if fmap' id = id then fmap' is fmap.
The free theorem for:
fmap' :: forall a b. (a -> b) -> F a -> F b
assumes that F is already a Functor. That is, it shows that if there
exists a valid fmap instance for F, then for any other function fmap'
with the same signature as fmap, fmap' id = id implies fmap' = fmap.
So if you want to invent a data type and fmap instance which satisfies
law 1 but not law 2, then it needs to be a data type for which no valid
fmap instance is possible *at all*.
So it doesn't rule out the possibility completely, but it narrows down
the search space considerably.
Cheers,
Andrew Bromage
More information about the Haskell-Cafe
mailing list