Editing Fixed-point combinator (section)

=== Lazy functional implementation ===

In a language that supports [[lazy evaluation]], as in [[Haskell]], it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator which is conventionally named <code>fix</code>. Since Haskell has lazy [[data type]]s, this combinator can also be used to define fixed points of data constructors (and not only to implement recursive functions). The definition is given here, followed by some usage examples. In Hackage, the original sample is:<ref>[https://hackage.haskell.org/package/base-4.10.0.0/docs/src/Data.Function.html#fix The original definition in Data.Function].</ref>

<syntaxhighlight lang="haskell">
fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
                                 -- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
  where fac f 0 = 1
        fac f x = x * f (x-1)

fact 5                           -- evaluates to 120
</syntaxhighlight>