[Caml-list] Recursive modules and polymorphic recursion

[brogoff@speakeasy.net]

Hi,
    I was playing with the recursive modules in the CVS snapshot and much to 
my chagrin the very first pr function of the very first pr example in Okasaki 
causes the system to barf, where barf means "Cannot safely evaluate the 
definition of the recursively-defined module RAListImpl". Is this a temporary 
limitation of the CVS version or a permanent limitation of the feature? 
I've appended the code to this email.

    You can write these pr examples from Okasaki using the nested polymorphism 
on record fields (or polymorphic methods if you like objects) so I guess it's 
time again to raise the question of when we will get a direct way to write these 
functions, say with explicit type annotations on the functions. The recursive 
module approach would be acceptable, but even if it worked here it has the 
(minor) disadvantage of requiring you to create a module where you have to 
expose functions you'd prefer to have hidden, which you can then export with 
your final signature. 

-- Brian

module rec RAListImpl :
    sig
      type 'a ra_list

      val empty   : 'a ra_list
      val is_empty : 'a ra_list -> bool
      val length  : 'a ra_list -> int
(*
      val cons    : 'a -> 'a ra_list -> 'a ra_list
      val uncons    : 'a ra_list -> 'a * 'a ra_list
      val head    : 'a ra_list -> 'a
      val tail    : 'a ra_list -> 'a ra_list
      val lookup  : int -> 'a ra_list -> 'a

      val fupdate  : ('a -> 'a) -> int -> 'a -> 'a ra_list -> 'a ra_list
      val update  : int -> 'a -> 'a ra_list -> 'a ra_list
*)
    end =
  struct
    type 'a ra_list = Nil
    | Zero of ('a * 'a) ra_list
    | One of 'a * ('a * 'a) ra_list

    let empty = Nil
    let is_empty = function Nil -> true | _ -> false

    let length = function
        Nil -> 0
      | Zero ra -> 2 * (RAListImpl.length ra)
      | One (_,ra) -> 1 + 2 * (RAListImpl.length ra)

(*
    let cons x = function
        Nil -> One (x, Nil)
      | Zero ps -> One (x, ps)
      | One (y,b) -> Zero (RAListImpl.cons (x, y) b)

    let uncons = function
        Nil -> raise Not_found
      | One (x,Nil) -> (x,Nil)
      | One (x,ps) -> (x, Zero ps)
      | Zero ps ->
          let ((x,y),ps') = RAListImpl.uncons ps in
          (x, One (y, ps'))

    let lookup i l =
      match i,l with
        (i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> x
      | (i, One (x, ps)) -> RAListImpl.lookup (pred i) (Zero ps)
      | (i, Zero ps) ->
          let (x, y) = RAListImpl.lookup (i / 2) ps
          in if i mod 2 = 0 then x else y

    let head xs = let (x, _) = RAListImpl.uncons xs in x
    let tail xs = let (_, xs') = RAListImpl.uncons xs in xs'

    let fupdate f i l =
      match i,l with
        (i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> One (f x, ps)
      | (i, One (x, ps)) ->
          cons x (RAListImpl.fupdate f (i-1) (Zero ps))
      | (i, Zero ps) ->
          let f' (x, y) = if i mod 2 = 0 then (f x, y) else (x, f y) in
          Zero (RAListImpl.fupdate f' (i / 2) ps)

    let update  i y xs = RAListImpl.fupdate (fun x -> y) i xs
*)
  end

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners