fix

<mathematics>

1. The fixed point combinator. Called Y in combinatory logic. Fix is a higher-order function which returns a fixed point of its argument (which is a function). 

 fix :: (a -> a) -> a
 fix f = f (fix f)
Which satisfies the equation 

 fix f = x such that f x = x.
Somewhat surprisingly, fix can be defined as the non-recursive lambda abstraction: 

 fix = \ h . (\ x . h (x x)) (\ x . h (x x))
Since this involves self-application, it has an infinite type. A function defined by 

 f x1 .. xN = E
can be expressed as 

 f = fix (\ f . \ x1 ... \ xN . E)
   = (\ f . \ x1 ... \xN . E)
 	(fix (\ f . \ x1 ... \ xN . E))
   = let f = (fix (\ f . \ x1 ... \ xN . E))
     in \ x1 ... \xN . E
If f does not occur free in E (i.e. it is not recursive) then this reduces to simply 

 f = \ x1 ... \ xN . E
In the case where N = 0 and f is free in E, this defines an infinite data object, e.g. 

 ones = fix (\ ones . 1 : ones)
      = (\ ones . 1 : ones) (fix (\ ones . 1 : ones))
      = 1 : (fix (\ ones . 1 : ones))
      = 1 : 1 : ...
Fix f is also sometimes written as mu f where mu is the Greek letter or alternatively, if f = \ x . E, written as mu x . E.

Compare quine.

[Jargon File]

Last updated: 1995-04-13

2. bug fix.

Last updated: 1998-06-25

Nearby terms:

FITNR ♦ FITS ♦ FIX ♦ fix ♦ fixed disk ♦ fixed point ♦ fixed-point ♦ fixed point combinator

Try this search on Wikipedia, Wiktionary, Google, OneLook.

Loading