fixpoint operator that works with functions of different numbers of arguments
Author Message fixpoint operator that works with functions of different numbers of arguments

Here's a cute procedure you might enjoy if you haven't seen it before.
We want to write a fixpoint operator, such that

((fix G) x y z ...) = ((G (fix G)) x y z ...)

That is, such that

(apply (fix G) (list x y z ...)) = (apply (G (fix G)) (list x y z ...))

So using unrestricted lambda, one simply writes down the right hand side,
naming the list args (or whatever):

(define fix
(lambda (G)
(lambda args
(apply (G (fix G)) args))))

Then you can use this to do the usual stuff you can do with a fix
point combinator.  For example...

(define fact-gen
(lambda (fact)
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1)))))))

(define factorial (fix fact-gen))

Of course, you can write fix without using recursion
(the famous Y combinator).  But if you're just interested
in taking fixpoints for computation, and not in explaining
the semantics of features like define and letrec,
then the above definition of fix is adequate.

Gary Leavens

--
229 Atanasoff Hall, Department of Computer Science

phone: (515)294-1580 fax: (515)294-0258 ftp site: ftp.cs.iastate.edu
URL: http://www.*-*-*.com/ ~leavens/homepage.html

Sat, 07 Mar 1998 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages

Powered by phpBB® Forum Software