Re: [Caml-list] Problem with polymorphic letrec

[Tyng-Ruey Chuang <trc@iis.sinica.edu.tw>]

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