From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id GAA03902; Thu, 26 Jun 2003 06:58:55 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
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 GAA03685 for <caml-list@pauillac.inria.fr>; Thu, 26 Jun 2003 06:58:53 +0200 (MET DST)
Received: from mail.speakeasy.net (mail15.speakeasy.net [216.254.0.215])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5Q4wqf17882
	for <caml-list@inria.fr>; Thu, 26 Jun 2003 06:58:52 +0200 (MET DST)
Received: (qmail 29073 invoked from network); 26 Jun 2003 04:58:50 -0000
Received: from unknown (HELO grace.speakeasy.org) ([216.254.0.2])
          (envelope-sender <brogoff@speakeasy.net>)
          by mail15.speakeasy.net (qmail-ldap-1.03) with DES-CBC3-SHA encrypted SMTP
          for <caml-list@inria.fr>; 26 Jun 2003 04:58:50 -0000
Date: Wed, 25 Jun 2003 21:58:50 -0700 (PDT)
From: brogoff@speakeasy.net
To: caml-list@inria.fr
Subject: [Caml-list] Recursive modules and polymorphic recursion
Message-ID: <Pine.LNX.4.44.0306252139470.32188-100000@grace.speakeasy.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Spam: no; 0.00; brogoff:01 recursion:01 chagrin:01 okasaki:01 barf:01 annotations:01 disadvantage:01 val:01 uncons:01 fupdate:01 struct:01 bool:01 speakeasy:01 sig:01 permanent:98 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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