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)
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
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:19 MET