fix

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 = 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)

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