[Caml-list] Problem with polymorphic letrec

[Caml-list] Problem with polymorphic letrec

[Matteo Frigo]

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

Re: [Caml-list] Problem with polymorphic letrec

[Chris Quinn]

> 
> 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?

You can certainly get the polymorphism back by abstracting out
the main functionality:

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

then :
let polymul = polymul_aux polymul_f

But maybe, ultimately, that will not be the problem!

I don't know if it has any relevance at all but the -rectypes
flag can sometimes help.
For instance:

type key
type 'data map = (key * ('data * 'data map)) list

This is a type which will not typecheck without -rectypes
but it is definitely meaningful and useful to me!

Chris Q.
-------------------
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

Re: [Caml-list] Problem with polymorphic letrec

[Tyng-Ruey Chuang]

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

If you are certain the definition of a polymorphically recursive
function f is type-safe, you can use "(Obj.magic f)" in the
body of f to coerce the inferred type of f into one that is
not constrained, so the definition of f can be type-checked.

Note that Obj.magic has type

	Obj.magic: 'a -> 'b

so it in fact bypasses the type system. Use with care. :-)

Still I find it useful when defining map functions
of "nested datatypes" like Nested.map below.

Have fun!

Tyng-Ruey

---------

module Pair =
struct
  type 'a t = 'a * 'a
  let map f (x, y) = (f x, f y) 
end

module Node =
struct 
  type ('a, 'b) t = Nil | Cons of 'a * 'b
  let map (f, g) x =
      match x with
            Nil -> Nil
          | Cons (x, y) -> Cons (f x, g y)
end 

module Nested = 
struct
  type 'a t = Rec of ('a, 'a Pair.t t) Node.t

  let rec map f (Rec x) =
      Rec (Node.map (f, Obj.magic map (Pair.map f)) x)   (*** HERE ***)
end                                                                          

let n0 = Nested.Rec  Node.Nil
let n1 = Nested.Rec (Node.Cons (((1,2),(3,4)), n0))
let n2 = Nested.Rec (Node.Cons ((1,2), n1))
let n3 = Nested.Rec (Node.Cons (1, n2))

let double x = x + x
let square x = x * x

(* Some test cases *)

let d3 = Nested.map double n3
let f3 = Nested.map string_of_int  (Nested.map square n3)

-------------------
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