CODEWITHSUNDEEP
haskellrecursionfixpoint-combinators
Jean-Baptiste Zeller
Jean-Baptiste Zeller

Reputation: 37

Haskell type and fix recursion examples

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?

Upvotes: 1

Views: 133

Answers (1)

Lee
Lee

Reputation: 144126

You can read the type of the lambda as:

(b -> b) -> (b -> b)

which may make it clearer what happens when you provide it to fix. The returned value is another function b -> b which it then immediately applied with the argument 5 in your example.

Upvotes: 1

Related Questions