You are here: irt.org | FOLDOC | fix

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 = Ecan 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 . EIf f does not occur free in E (i.e. it is not recursive) then this reduces to simply

f = \ x1 ... \ xN . EIn 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.

(1995-04-13)

2. bug fix.

(1998-06-25)

Nearby terms: FITNR « FITS « FIX « **fix** » fixed disk » fixed point » fixed-point

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL