How to use the fix and how does it work?

Question

I was a bit confused by the documentation for fix (although I think I understand what it should do now), so I looked at the source code. This left me more confused:

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

How exactly does this return a fixed point?

I decided to try on the command line:

 Prelude Data.Function> fix id ... 

And he hangs there. Now, to be fair, this is on my old macbook, which is a bit slow. However, this function cannot be too expensive, because everything that is passed in id returns the same thing (not to mention the fact that it does not consume CPU time). What am I doing wrong?

Answer 1

You are not doing anything wrong. fix id is an infinite loop.

When we say that fix returns the least fixed point of a function, we mean this in the sense of domain theory . So fix (\x → 2*x-1) will not return 1 , because although 1 is a fixed point of this function, it is not the smallest in the order of domains.

I cannot describe the domain order in one or two paragraphs, so I am referring you to the domain theory link above. This is a great tutorial, easy to read, and quite instructive. I highly recommend it.

For a view from 10,000 feet, fix is a higher order function that encodes the idea of ​​recursion. If you have an expression:

 let x = 1:x in x 

The result is an endless list [1,1..] , you can say the same thing using fix :

 fix (\x -> 1:x) 

(Or just fix (1:) ), which says that find me a fixed point on the function (1:) , IOW the value of x is such that x = 1:x ... exactly the same as we defined above. As you can see from the definition, fix is nothing more than this idea - recursion encapsulated in a function.

This is really a general recursion concept — you can write any recursive function in this way, including functions that use polymorphic recursion . So, for example, a typical Fibonacci function:

 fib n = if n < 2 then n else fib (n-1) + fib (n-2) 

You can write using fix as follows:

 fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2)) 

Exercise: Expand the definition of fix to show that these two definitions of fib equivalent.

But for a complete understanding, read about domain theory. These are really cool stuff.

Answer 2

I do not claim to understand this at all, but if it helps someone ... then yippee.

Consider the definition of fix . fix f = let x = fx in x . The stunning part is that x is defined as fx . But think about it for a moment.

 x = fx 

Since x = fx, we can substitute the value x on the right side of this value, right? So therefore ...

 x = f . f $ x -- or x = f (fx) x = f . f . f $ x -- or x = f (f (fx)) x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc. 

So, the trick is for f to generate some structure so that later f can match this structure and complete the recursion without worrying about the full “value” of its parameter (?)

Unless, of course, you want to do something like creating an infinite list, as shown by luqui.

TomMD factorial explanation is good. Fixed signature of type (a -> a) -> a . A typical signature for (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) is (b -> b) -> b -> b , in other words, (b -> b) -> (b -> b) . So we can say that a = (b -> b) . So fix accepts our function, which is a -> a or indeed (b -> b) -> (b -> b) , and will return a result of type a , in other words, b -> b , in other words, another function !

Wait, I thought it was supposed to return a fixed point ... not a function. Well, it does, sort of (because functions are data). You can imagine that this gave us the final function to search for factorial. We gave him a function that cannot recursively (therefore, one of the parameters to it is the function used for recursion), and fix taught it recursively.

Remember, as I said, f must generate some structure so that later f matches the pattern and ends? Well, that is not entirely true, I think. TomMD has illustrated how we can extend x to apply a function and move on to the base case. For his function, he used if / then, and that is what causes the termination. After repeated replacements, the in part of the entire definition of fix eventually ceases to be defined in terms of x , and this is when it is computable and complete.

Answer 3

You need the endpoint to complete. Extending your example, it is obvious that it will not end:

 fix id --> let x = id x in x --> id x --> id (id x) --> id (id (id x)) --> ... 

Here is a real example of how I use the fix (note that I often don’t use the fix and was probably tired / not worried about the code being read when I wrote this):

 (fix (\fh -> if (pred h) then f (mutate h) else h)) q 

WTF, you say! Well, yes, but there are a few really useful points here. First of all, your first argument to fix should usually be a function, which is the "recurse" case, and the second argument is the data that should act. Here is the same code as the named function:

 getQ h | pred h = getQ (mutate h) | otherwise = h 

If you are still confused, perhaps factorial will become a simpler example:

 fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120 

Pay attention to the rating:

 fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 --> let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 --> let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 --> let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3 

Oh, did you just see it? This x has become a function within our then branch.

 let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) --> let x = ... in 3 * x 2 --> let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 --> 

In the above example, you need to remember x = fx , therefore, the two arguments are x 2 at the end, not just 2 .

 let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 --> 

And I will stay here!

Answer 4

One clear definition You may have invented a fix again!

Answer 5

As I understand it, it finds the value for the function, so that it outputs the same thing that you give it. There is a catch, he will always choose undefined (or an infinite loop, in haskell, undefined and infinite loops are the same), or something that has the most undefined in it. For example, with id,

 λ <*Main Data.Function>: id undefined *** Exception: Prelude.undefined 

As you can see, undefined is a fixed point, so fix will choose this. If you instead execute (\ x-> 1: x).

 λ <*Main Data.Function>: undefined *** Exception: Prelude.undefined λ <*Main Data.Function>: (\x->1:x) undefined [1*** Exception: Prelude.undefined 

So fix cannot select undefined. To make it a little more connected with infinite loops.

 λ <*Main Data.Function>: let y=y in y ^CInterrupted. λ <*Main Data.Function>: (\x->1:x) (let y=y in y) [1^CInterrupted. 

Again, a little difference. So what is a fixed point? Let's try repeat 1 .

 λ <*Main Data.Function>: repeat 1 [1,1,1,1,1,1, and so on λ <*Main Data.Function>: (\x->1:x) $ repeat 1 [1,1,1,1,1,1, and so on 

It is the same! Since this is the only fixed point, fix must rely on it. Sorry fix , there are no endless loops or undefined for you.