FIX


Meaning of FIX in English

1. < mathematics > 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 ]

(1995-04-13)

2. bug fix .

(1998-06-25)

FOLDOC computer English dictionary.      Английский словарь по компьютерам FOLDOC.