When reading about fix because I was interested in having recursive lambdas in my code I came upon this particular example of code (from Here):
fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 Now ignoring the type signature of fix I feel something's wrong with that piece of code :
The type of fix is (a -> a) -> a while the type of the lambda is (a -> a) -> a -> a I'm sure I'm reading this piece of code wrong but the way I first read it was "fix is applied to two argument" which is wrong because fix only accept one argument, a function (a -> a), there must be something I'm clearly missing.
I then looked at the type of the lambda, and the type of fix and it seemed to me "hang on, isn't there a huge mismatch? I can understand that with curried function you can feed a function of type a -> a -> a not enough argument to create a new function, but here I'm feeding (a -> a) -> a -> a to a (a -> a) -> a functions, it seems like I'm trying to pass an elephant through a pinhole, feeding the wrong argument to the fix function.
Where did my internal parser and type checker (brain 1.0) go wrong in evaluating this line?
a, it must be the same type. This is not the case - when you have a functionfix :: (a -> a) -> awhat you really have isforall a . (a -> a) -> a. Hereacan be instantiated to any type at all. In this case, you havea ~ (x -> x)sofix :: ((x -> x) -> (x -> x)) -> x -> xtakes two arguments.