In the literature a polyvariadic fix-point combinator is often presented using "...", or ellipsis. For example,

(letrec ((f1 e1) (f2 e2) ... (fn en) ) e)

(let ((fs (Y* (lambda (f1 f2 ... fn) e1) ... (lambda (f1 f2 ... fn) en)))) (apply (lambda (f1 f2 ... fn) e) fs))

We start by recalling how ordinary general recursion is represented via the ordinary fix-point combinator such as Y . A recursive function like fact :

let rec fact : int -> int = fun n -> if n <= 0 then 1 else n * fact (n-1)

let open_fact : (int -> int) -> int -> int = fun self n -> if n <= 0 then 1 else n * self (n-1)

This function is no longer recursive. The fix-point combinator

val fix : (('a->'b) -> ('a->'b)) -> ('a->'b)

fix open_fact;; (* - : int -> int = <fun> *) fix open_fact 5;; (* - : int = 120 *)

We now generalize to mutual recursion, on the familiar example of determining if a natural number is even or odd:

let rec even : int -> bool = fun n -> n = 0 || odd (n-1) and odd : int -> bool = fun n -> n <> 0 && even (n-1)

evod

type idx = int let rec evod : idx -> int -> bool = function | 0 -> fun n -> n = 0 || evod 1 (n-1) | 1 -> fun n -> n <> 0 && evod 0 (n-1) let even = evod 0 and odd = evod 1

idx

evod

fact

let open_evod : ((idx -> int -> bool) as 't) -> 't = fun self -> function | 0 -> fun n -> n = 0 || self 1 (n-1) | 1 -> fun n -> n <> 0 && self 0 (n-1)

let evod = fix open_evod (* val evod : idx -> int -> bool = <fun> *) let even = evod 0 and odd = evod 1 (* val even : int -> bool = <fun> *) (* val odd : int -> bool = <fun> *)

We thus obtain that the polyvariadic fix-point combinator

let fix_poly_v1 : ('t ->'t) -> ((idx -> 'a -> 'b) as 't) = fix

fix_poly_v1

open_evod

We now derive a mutual fix-point combinator with the better interface and efficiency. We wish the fix-point combinator took a list of functions in the open recursion style, returning the list of functions with their knots tied-up. Ideally, the running example should look like

let [even;odd] = let open_even [even;odd] = fun n -> n = 0 || odd (n-1) and open_odd [even;odd] = fun n -> n <> 0 && even (n-1) in fix_poly [open_even;open_odd]

val fix_poly : (('a -> 'b) list -> ('a -> 'b)) list -> ('a -> 'b) list

fix_poly_v1

idx -> t

t

[0..n-1]

idx

n

t list

let fix_poly_temp : (('a -> 'b) list -> 'a -> 'b) list -> ('a -> 'b) list = fun l -> let n = List.length l in let clause self idx = (List.nth l idx) (List.map self (iota n)) in List.map (fix_poly_v1 clause) (iota n)

where iota n produces a list of integers 0 through n-1 . This combinator has two problems: divergence and inefficiency. The former is easy to fix with the appropriate eta-expansion

let fix_poly_v2 : (('a -> 'b) list -> 'a -> 'b) list -> ('a -> 'b) list = fun l -> let n = List.length l in let clause self idx x = (List.nth l idx) (List.map self (iota n)) x in let tied idx x = fix clause idx x in List.map tied (iota n)

giving us a polyvariadic fix-point combinator with the desired interface. List.nth and iota strongly remind of Queinnec's NfixN2 , described in his book ``LISP In Small Pieces''. However, not only List.nth (in Scheme, list-ref ) is inefficient (indexing a list requires its traversal and hence is not constant time), it is also aesthetically displeasing. Ideally, the list of clauses should be handled as an abstract collection, using only operations like fold or map rather than random-access List.nth . It would be easy then to generalize to other collections, such as tuples.

We now improve the efficiency of fix_poly_v2 , getting rid of List.nth . The starting point is the simpler fix_poly_temp : we can always fix the divergence later, with eta-expansion. Let fl be fix_poly_temp l for some appropriate list l and let clause = fun self idx -> (List.nth l idx) (List.map self (iota n)) . We calculate

fl === fix_poly_temp l === map (fix clause) (iota n) {fixpoint} === map (clause (fix clause)) (iota n) {inline the first clause, beta-reduce} === map (fun idx -> List.nth l idx (map (fix clause) (iota n))) (iota n) {Recall, map (f . g) l === map f . map g l, and map (fun idx -> List.nth l idx) (iota (List.length l)) === l } === map (fun li -> li (map (fix clause) (iota n))) l === {recall what fix_poly_temp l is} === map (fun li -> li (fix_poly_temp l)) l

The result shows that fix_poly_temp l is an ordinary fix-point, of fun self -> map (fun li -> li self) l . The result is immediately usable in Haskell. In OCaml, we have to introduce a few eta-expansions to prevent premature looping.

let fix_poly : (('a -> 'b) list -> 'a -> 'b) list -> ('a -> 'b) list = fun l -> fix (fun self l -> List.map (fun li x -> li (self l) x) l) l

The combinator fix_poly is straightforward to translate into Scheme. After inlining the definition of the ordinary fix-point combinator and simplifying, we obtain the following expression for the polyvariadic fix-point combinator. It is notably simpler than the polyvariadic combinators by Queinnec and Goldberg.

(define (Y* . l) ((lambda (u) (u u)) (lambda (p) (map (lambda (li) (lambda x (apply (apply li (p p)) x))) l))))

Compared to the OCaml version, the functions to obtain the mutual fix-point of do not have to have the same number of arguments (the same arity). The accompanying code shows an example.

The combinator fix_poly translates to Haskell trivially. Since Haskell is non-strict, no eta-expansions are needed. The result is a one-liner:

fix_poly:: [[a]->a] -> [a] fix_poly fl = fix (\self -> map ($ self) fl) where fix f = f (fix f) test1 = (map iseven [0..5], map isodd [0..5]) where [iseven, isodd] = fix_poly [fe,fo] fe [e,o] n = n == 0 || o (n-1) fo [e,o] n = n /= 0 && e (n-1)

The type of fix_poly points out the remaining problem: all mutually dependent clauses are restricted to the same type. This is a serious limitation. The type of fix_poly has a curious structure, which shows the way out, through the second-order Functor :

class Functor2 c where fmap2 :: (forall a. c1 a -> c2 a) -> c c1 -> c c2

c

c1

newtype Id a = Id{unId :: a} newtype P3 a1 a2 a3 c = P3 (c a1, c a1, c a3) instance Functor2 (P3 a1 a2 a3) where fmap2 f (P3 (x,y,z)) = (P3 (f x, f y, f z))

fix_gen_poly:: Functor2 c => c ((->) (c Id)) -> c Id fix_gen_poly fl = fix (\self -> fmap2 (\x -> Id (x self)) fl) where fix f = f (fix f)