fix
Technology Dictionary
-> fix
Search:
fix
fix
Technology Dictionary
-> fix
Search:
fix
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]
(1995-04-13)
2. bug fix.
(1998-06-25)
©
Art Branch Inc.
SQL Tutorial