To start with the function
fun xss = \f -> let ope x y = x . f . y in foldr1 ope xss
I'll rewrite this as
fun xss f = foldr1 ope xss
where ope x y = x . f . y
So we start with foldr1
:
foldr1 :: (a -> a -> a) -> [a] -> a
So we can break down
foldrl1
ope -- (a -> a -> a)
xss -- [a]
So ope :: a -> a -> a
, this is really useful to know since it simplifies the types of x
and y
to be restricted entirely to a
, or put another way they both have the same type. Since they're both functions (as required by .
), instead of unifying their types the long way I'll just say that x, y :: b -> c
ope x y = x . f . y
-- (b -> c) . (s -> t) . (b -> c)
I've left f
's type as unknowns right now, other than specifying that it has to be a function. Since we know that x
and y
have the same type, we can now say that y
's output type is the same as f
's input type, so s ~ c
, and f
's output type has to be the same as x
's input type, so t ~ b
, so we get
ope x y = x . f . y
-- (b -> c) . (c -> b) . (b -> c)
So now we can fill fun
's signature. We already know the type of xss
, it's a ~ b -> c
, and since foldr1
's output type is also a
, we get
fun :: [b -> c] -> (c -> b) -> (b -> c)
And indeed this is the type that GHCi
gives us