This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: [Caml-list] Problem with polymorphic letrec
• Tyng-Ruey Chuang
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2001-09-24 (06:28) From: Tyng-Ruey Chuang Subject: Re: [Caml-list] Problem with polymorphic letrec
```> ... 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?
>
> 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

```