1. Cs> The fixed pointCombinator. 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)
