Version française
Home     About     Download     Resources     Contact us    
Browse thread
Polymorphic recursion in modules - impossible?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Markus Mottl <mottl@m...>
Subject: Polymorphic recursion in modules - impossible?
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