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 IAA05120; Mon, 24 Sep 2001 08:28:46 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
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 IAA05109 for <caml-list@pauillac.inria.fr>; Mon, 24 Sep 2001 08:28:45 +0200 (MET DST)
Received: from mail.iis.sinica.edu.tw (mail.iis.sinica.edu.tw [140.109.20.50])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f8O6ShX07814
	for <caml-list@inria.fr>; Mon, 24 Sep 2001 08:28:43 +0200 (MET DST)
Received: (from trc@localhost)
	by mail.iis.sinica.edu.tw (8.10.2/8.10.2) id f8O6PZg09586;
	Mon, 24 Sep 2001 14:25:35 +0800 (CST)
From: Tyng-Ruey Chuang <trc@iis.sinica.edu.tw>
Message-Id: <200109240625.f8O6PZg09586@mail.iis.sinica.edu.tw>
Subject: Re: [Caml-list] Problem with polymorphic letrec
To: athena@fftw.org (Matteo Frigo)
Date: Mon, 24 Sep 2001 14:25:35 +0800 (CST)
Cc: caml-list@inria.fr, trc@iiserv.iis.sinica.edu.tw
In-Reply-To: <m3d74qhmf8.fsf@glauke.fftw.org> from "Matteo Frigo" at Sep 16, 2001 05:10:19 PM
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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