
/* Fixed point combinator examples (originally written by Klaus Barthelmann
   08-1993, completely revised 06-2006 by Albert Graef). */

/* Fixed point combinators are characterized by the property that they compute
   fixed points of a function, i.e., G is a fixed point combinator iff G F = F
   (G F) for each (higher-order) function F. They provide a way to implement
   "anonymous recursion", i.e., define recursive functions using nothing but
   simple lambda abstractions. The basic idea is that the function is defined
   in terms of a second lambda abstraction which takes the function itself as
   an extra "placeholder" argument and performs a "single step" of the
   recursion. See, e.g., http://en.wikipedia.org/wiki/Y_combinator for
   details. */

/* The applicative order fixed point combinator ("Z combinator"), straight
   from the textbook. */

_Z = \F.(\X.F (\Y. X X Y)) (\X.F (\Y. X X Y));

/* The normal order fixed point combinator ("Y combinator"). Here the textbook
   version, _Y = \F.(\X.F (X X)) (\X.F (X X)), must be slightly modified to
   make it work in Q, since normally Q's eager evaluation strategy would loop
   on _Y F. The trick is to break the infinite recursion by placing quotes at
   the right places. This will defer the recursive evaluations until the
   function value is actually needed. We just have to remember that in the
   definition of the "single step" function the quotes then have to be
   stripped again from the function placeholder argument (see below for
   examples). */

_Y = \F.(\X.F '(X X)) (\X.F '(X X));

/* Example 1: the factorial. Note the ' before the function placeholder
   argument in the Y combinator version, which is needed to get rid of the
   extra quotes in the definition of _Y. */

zfact = _Z (\F X.if X<=0 then 1 else X*F (X-1));

yfact = _Y (\'F X.if X<=0 then 1 else X*F (X-1));

/* Example 2: the stream of all Fibonacci numbers. Note the extra "dummy"
   argument in the Z combinator version. Also note the embedded lambda in the
   body of the iterated function, which makes sure that the function argument
   only needs to be evaluated once in the lambda body. (If we don't do this
   then the running time will grow exponentially.)  */

zfibs = _Z (\F X.lazy {0,1|(\F.zipwith (+) F (tl F)) (F X)}) ();

yfibs = _Y (\'F.lazy {0,1|(\F.zipwith (+) F (tl F)) F});

/* Helper function to print the elements of a stream (ex.: `print zfibs'). */

print = do (\X.printf "%s\n" $ str X || flush);
