Search code examples
haskellfunctional-programmingfixpoint-combinators

Guessing the type of fixed-point combinator

My question is related to "fixed point combinator". According to this Wikipedia page section a function fix such that

fix f = f (fix f)

is of type (or at least can be of type)

(a -> a) -> a

Can someone explain me why?

Solution

  • Start from the definition

    fix f = f (fix f)

    Since it takes an argument, fix must have a type that looks like

    fix :: x -> y

    It applies its argument to something, so in fact

    fix :: (p -> q) -> r

    It actually applies its argument to fix f, so

    fix :: (r -> q) -> r

    The final result is actually the result of this application, so

    fix :: (r -> r) -> r