[Caml-list] Problem with polymorphic letrec

[Matteo Frigo <athena@fftw.org>]

I am trying to implement polynomial multiplications in ocaml and I ran
into the following problem.

I want to represent polynomials as functions int -> 'a , where 'a is
the type of coefficients.  If function p represents the polynomial p0
+ p1 x + ... , then (p 1) returns p1 and so on.  Coefficients can
themselves be polynomials.

I want to implement polynomial multiplication as a function

   polymul mul p q

that takes ``mul'' (the multiplication operation of the coefficients),
two polynomials ``p'' and ``q'', and returns the product polynomial.
(Ignore for now the fact that I also need to pass the addition
operator for coefficients.)

I want to implement the so-called Agarwal-Cooley algorithm for
polynomial multiplication.  To multiply p and q, the algorithm maps
p(x) into a polynomial in two variables p(y,z), and similarly for
q(y,z).  p(y,z) is a polynomial in y whose coefficients are
polynomials in z.  Then, the algorithm recursively multiplies p(y) by
q(y), using itself recursively as multiplication operation for the
coefficients.

Ignoring the base case of the recursion and the details of the
algorithm, I therefore need to code something like

let rec polymul mul p q =
   polymul (polymul mul) (fun _ -> p) (fun _ -> q)

This expression does not typecheck in ocaml 2 because polymul is used
polymorphically within its own body.

I could not come up with any hack to code polymul without changing the
representation of polynomials, which I'd rather not change for other
reasons.  

Any suggestion on how to work around this problem?

Thanks in advance,
Matteo Frigo

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr