Is there a fixed point combinator for creating tuples of mutually recursive functions? I.e. I'm looking for something like the Y-Combinator but which takes multiple "recursive"* functions, and will return a tuple of functions?
*: not really recursive of course, as they are written to take themselves (and siblings) as arguments, in the usual Y-Combinator way.
The following web page describes the fix-point combinators for mutual recursion (polyvariadic fixpoint combinators) in detail. It derives the simplest so far combinator. http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic
For ease of reference, here is the simplest polyvariadic combinator in Haskell (one-liner)
fix_poly:: [[a]->a] -> [a]
fix_poly fl = fix (\self -> map ($ self) fl)
where fix f = f (fix f)
and here it is in Scheme, a strict language
(define (Y* . l)
((lambda (u) (u u))
(lambda (p)
(map (lambda (li) (lambda x (apply (apply li (p p)) x))) l))))
Please see the web page for examples and more discussion.
I'm not entirely sure about this one. I'm still trying to find a formal proof of it. But it seems to me you don't need one. In Haskell, if you have something like:
fix :: (a -> a) -> a
fix f = let x = f x in xmain = let { x = ... y ...; y = ... x ... } in x
you can rewrite main to
main = fst $ fix $ \(x, y) -> (... y ..., ... x ...)
But like I said, I'm not 100% sure about this one.
