Haskell "fix" keyword failed on declaring a recursive lambda function

Question

Seems a function should have a name to be recursive(in order to call itself), so how does a lambda function be recursive?

I searched wikipedia and it says this could be done by a "Y-combinator". I don't have much math theory backgroup, it just tell me that "Y-combinator" is discovered by Haskell himself. Called "fix" keyword in Haskell language, I tried:

Prelude> let fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

<interactive>:17:12: Not in scope: ‘fix’

Seems failed, but how to use "fix" keyword to do what I expected?

Answer 1

fix is defined as:

fix :: (a -> a) -> a
fix f = let x = f x in x

so it expands into f (f (f (f ...))) i.e. an infinite sequence of nested applications of the input function f to some parameter x.

You can give your lambda function a top-level definition e.g.

factF f n = if n == 0 then 1 else n * f (n - 1)

or equivalently:

factF :: (Int -> Int) -> (Int -> Int)
factF f = \n -> if n == 0 then 1 else n * f (n - 1)

you can provide this function to fix to obtain a function (Int -> Int) i.e.

fact :: (Int -> Int)
fact = fix factF

if you expand this definition you get

factF (factF (factF (factF ...)))
=> \n -> if n == 0 then 1 else (factF (factF (factF ...)))

due to laziness, the repeated applications of factF are only evaluated if n /= 0 so the above function applied to 0 will evaluate immediately to 1.

You can see in this expansion that factF is being provided as an argument to itself which it then applies to smaller version of n. Since factN is the same as your lambda function, the same thing is happening there - the parameter f inside the lambda is the lambda itself which it can then call recursively.

Answer 2

fix is not a keyword, it is a function defined in the Data.Function module. Therefore, to use it, you must import that module.

import Data.Function

or in GHCi:

:m Data.Function