Fixed point combinator for mutually recursive functions?

Question

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.

Answer 1

The creature you are looking for is Y* combinator.

Basing on this page by oleg-at-okmij.org I ported the Y* to Clojure:

(defn Y* [& fs]
  (map (fn [f] (f))
    ((fn [x] (x x))
      (fn [p]
        (map
          (fn [f]
            (fn []
              (apply f
                (map
                  (fn [ff]
                    (fn [& y] (apply (ff) y)))
                  (p p)))))
          fs)))))

The classic example of mutual recursive function is even/odd so here is the example:

(let
  [[even? odd?]
   (Y*
     (fn [e o]
       (fn [n]
         (or (= 0 n) (o (dec n)))))
     (fn [e o]
       (fn [n]
         (and (not= 0 n) (e (dec n)))))
     )
   ]
  (do
    (assert (even? 14))
    (assert (odd? 333))
    ))

You can easily blow the stack with this functions if you use big enough arguments, so here is trampolined version of it for example completeness which do not consume stack at all:

(let
  [[even? odd?]
   (Y*
     (fn [e o]
       (fn [n]
         (or (= 0 n) #(o (dec n)))))
     (fn [e o]
       (fn [n]
         (and (not= 0 n) #(e (dec n)))))
     )
   ]
  (do
    (assert (trampoline even? 144444))
    (assert (trampoline odd? 333333))
    ))

The Y* combinator is very useful for defining mutual recursive definitions of monadic parsers, of which I'll blog soon on lambder.com , stay tuned ;)

-- Lambder

Answer 2

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 x

main = 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.

Answer 3

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.