caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] Recursive modules and polymorphic recursion
@ 2003-06-26  4:58 brogoff
  2003-06-26 12:14 ` Xavier Leroy
  0 siblings, 1 reply; 3+ messages in thread
From: brogoff @ 2003-06-26  4:58 UTC (permalink / raw)
  To: caml-list

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


^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2003-06-26 13:15 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-06-26  4:58 [Caml-list] Recursive modules and polymorphic recursion brogoff
2003-06-26 12:14 ` Xavier Leroy
2003-06-26 13:15   ` brogoff

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).