[Haskell-cafe] how to factorize propagation of a function over a data type

TP paratribulations at free.fr
Tue Dec 3 02:30:11 UTC 2013


Andras Slemmer wrote:

> The reason you need the typeclass constraint is not in the use of 'f' but
> rather in the use of propagate and what you pass in to it (foo1/foo2
> here). If you leave away the typeclass constraint what you're left with
> is:
> 
> propagate' Bar -> (forall a. a->a) -> Bar
> 
> The implementation of this function is the same as before, however your
> use of propagate' is restricted:
> forall a. a->a is a very "strict" type, in fact the only inhabitant of
> this type is 'id' (and bottom, but disregard that here), which means the
> only way to call propagate is to pass in 'id'. Try it yourself!

Indeed I have tried, it works as you say.

> Related note: there is a proof that in fact the only inhabitant of (forall
> a. a -> a) is 'id' and it is the consequence of the "parametricity"
> property. It is a very neat result I suggest you look it up!

Interesting. I have tried to google on the topic, but I find mainly research 
articles. For example:

https://www.google.fr/search?client=ubuntu&channel=fs&q=haskell+%22parametricity+property%22&ie=utf-8&oe=utf-8&gws_rd=cr&ei=P_acUvboDse_0QX9mYDADQ#channel=fs&q=%22parametricity+property%22+haskell

Are there textbooks where a proof of this fact could be found? I'm an 
autodidact (who also benefits from help of guys like you), I don't know what 
lectures on type theory at university level could look like.

Thanks

TP



More information about the Haskell-Cafe mailing list