[Haskell-cafe] Expressing "self-composable" functions at the type level

Dan Doel dan.doel at gmail.com
Sun Nov 10 02:18:41 UTC 2013

On Sat, Nov 9, 2013 at 7:53 PM, Ignas Vyšniauskas <baliulia at gmail.com> wrote:
> I guess this is simply not type-able in System F?

There are System F types that can accomplish some cases of this; just
not Hindley-Milner types. For instance:

    twicePair :: (forall a. a -> (a, a)) -> (forall a. a -> ((a,a),(a,a)))
    twicePair f = f . f

That is, of course, very specific to your example. Doing significantly
better is harder, and I don't think you'll ever get to the real type
you want, which is:

    twice : ((a -> b) ∩ (b -> c)) -> a -> c

I.E. look up interstection types if you're into this stuff. They tend
to be less popular than quantifier-based polymorphism, though.

More information about the Haskell-Cafe mailing list