From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: weis
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA23936 for caml-redistribution; Wed, 3 Feb 1999 16:40:57 +0100 (MET)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA17238 for <caml-list@pauillac.inria.fr>; Mon, 1 Feb 1999 21:58:21 +0100 (MET)
Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id VAA11396
	for <caml-list@inria.fr>; Mon, 1 Feb 1999 21:58:19 +0100 (MET)
Received: (from mottl@localhost)
	by miss.wu-wien.ac.at (8.9.0/8.9.0) id VAA20331
	for caml-list@inria.fr; Mon, 1 Feb 1999 21:58:13 +0100 (MET)
From: Markus Mottl <mottl@miss.wu-wien.ac.at>
Message-Id: <199902012058.VAA20331@miss.wu-wien.ac.at>
Subject: Polymorphic recursion in modules - impossible?
To: caml-list@inria.fr (OCAML)
Date: Mon, 1 Feb 1999 21:58:13 +0100 (MET)
X-Mailer: ELM [version 2.4 PL21]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Sender: weis

Hello,

once again I have come across a problem concerning modules and recursion.
This time my question is how to get polymorphic recursion in functions
of modules.

Although I have read the FAQs about this topic and looked into the
archive of the mailing list, I couldn't find any solution to the problem -
I fear there is none.

Code example:
---------------------------------------------------------------------------
module RA_List =
struct
  type 'a ra_list = Nil
                  | Zero of ('a * 'a) ra_list
                  | One of 'a * ('a * 'a) ra_list

  let rec cons x = function
      Nil -> One (x, Nil)
    | Zero ps -> One (x, ps)
    | One (y,b) -> Zero (cons (x, y) ps)
end
---------------------------------------------------------------------------

It is clear that this piece of code cannot compile because of the
polymorphic recursion found in the last match of "cons".

The only trick applicable to this problem would be the one with references
to the function(s) that introduces polymorphic recursion.

The (unsolvable?) problem with this possibility is that one cannot
initialize the reference(s). This would have to happen after definition
and before application, but since modules are just a static means of
abstraction, one cannot do so - as opposed to the trick in the FAQs,
where there are no modules.

It would be nice if there were a solution to this, because this would
allow me the translation of the final two chapters of Okasaki's book to
OCAML. He uses (even if just as demonstration - SML also doesn't have
this feature) the technique of polymorphic recursion quite often there.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl