Haskell's type signature of u f=f.f is stronger than I would like

Question

I wrote the following simple function

u f=f.f

According to ghci this has the type signature of

u :: (b -> b) -> b -> b

However that type signature is too strict. Haskell is enforcing that our input be of type (b -> b) when it shouldn't necessarily need to be. For example the function (:[]) has the type signature of

(:[]) :: a -> [a]

Which is not of the form (b -> b), (unless you allow infinite types) and thus can't be passed to u. However you can compose (:[]) with itself.

g=(:[]).(:[])

This works and has the type

(:[]).(:[]) :: a -> [[a]]

So I should be, in principle, able to pass this to u.

I tried to write a new type signature myself to replace the generated signature but I could not come up with a way to express the requirements of the function. I always come up with the same type signature that the compiler provides. Is there a type signature we can give to weaken the u so that functions like (:[]) can be passed to it?

Answer 1

There are lots of different functions that can do this for specific cases, but none that work in general.

u1 :: (forall a. a -> f a) -> b -> f (f b)
u2 :: (forall a. f a -> a) -> f (f b) -> b

and infinitely more are possible. But the function

u f x = f (f x)

does not have a most general type in Haskell when RankNTypes is in play. As pigworker notes, there are type systems that can give u a principle type of the sort you desire, but they take type system extension in a very different direction from the ones that Haskell designers have focused on.