From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA31826; Sun, 16 Sep 2001 23:10:36 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA32470 for ; Sun, 16 Sep 2001 23:10:32 +0200 (MET DST) Received: from fftw.org (glauke.lcs.mit.edu [18.23.1.135]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f8GLATf03904 for ; Sun, 16 Sep 2001 23:10:29 +0200 (MET DST) Received: (from athena@localhost) by fftw.org (8.9.3/8.8.7) id RAA22533; Sun, 16 Sep 2001 17:10:20 -0400 X-Authentication-Warning: glauke.fftw.org: athena set sender to athena@fftw.org using -f To: caml-list@inria.fr Subject: [Caml-list] Problem with polymorphic letrec From: Matteo Frigo Date: 16 Sep 2001 17:10:19 -0400 Message-ID: User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.1 (Bryce Canyon) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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