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

[Alexander Vieth]

> Due to polymorphism this is not
> quite the same as saying that the domain and co-domain match.

I believe it's the same as saying that the type of the co-domain can be refined to the type of the domain. Self-composability is already expressed at the type level, although it may not be immediately clear.

In the case of swap, it might seem like it's not possible because (b, a) can be refined to (a, b) only if a = b, but when we compose swap with itself we get fresh names for the type variables, and (b, a) can indeed be refined to (a1, b1). Trying to type (swap . swap) we find that the first swap has type (a, b) -> (b, a) and the second swap has type (a1, b1) -> (b1, a1) so if we set b = a1 and a = b1 then we recover the type (b1, a1) -> (b1, a1).

Alex

On 2013-11-09, at 6:46 PM, Ignas Vyšniauskas wrote:

> Hi,
> 
> I'm wondering if there's some way to express that a function can be
> composed with itself at the type level. Due to polymorphism this is not
> quite the same as saying that the domain and co-domain match.
> 
> Example:
> 
> swap :: (a, b) -> (b, a)
> swap . swap :: (a, b) -> (a, b)
> 
> I'd like to write a function such as (in pseudocode):
> 
> involute :: ((a -> b) &&& (b -> a)) -> (a -> a)
> involute f = f . f
> 
> But I obviously can't write down the type for (a -> b) &&& (b -> a)
> 
> Perhaps this can be done with some typeclass hackery?
> 
> --
> Ignas
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe