From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.3 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 30C4CBC0A for ; Tue, 3 Apr 2007 14:49:22 +0200 (CEST) Received: from smtp5-g19.free.fr (smtp5-g19.free.fr [212.27.42.35]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l33CnLng018482 for ; Tue, 3 Apr 2007 14:49:21 +0200 Received: from [192.168.1.222] (vil93-4-82-227-140-227.fbx.proxad.net [82.227.140.227]) by smtp5-g19.free.fr (Postfix) with ESMTP id 7EEB241295; Tue, 3 Apr 2007 14:49:20 +0200 (CEST) Message-ID: <46124D4F.704@philippewang.info> Date: Tue, 03 Apr 2007 14:49:19 +0200 From: Philippe Wang User-Agent: Thunderbird 1.5.0.10 (Macintosh/20070221) MIME-Version: 1.0 To: Brian Hurt , ocaml ml Subject: Re: [Caml-list] How important are circular lists/recursive objects? References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46124D51.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursive:01 ocaml:01 recursive:01 rec':01 rec':01 val:01 mutable:01 mutable:01 val:01 iter:01 abstraction:01 hash:01 andrej:01 andrej:01 def:01 Brian Hurt wrote: > > In Ocaml you have some ability to define recursive data structures. > The classic example of this is the circular list: > > let rec example = 1 :: 2 :: example;; > > There are obvious limitations to this sort of trick: > > # let rec example = List.map (fun x -> x + 1) (1 :: 2 :: example);; > This kind of expression is not allowed as right-hand side of `let rec' > # > > The question is: if this behavior was completely outlawed, and either > you couldn't build up circular lists/recursive data structures of this > type at all, or had to call special functions (List.circularize, say), > to create them, would this be a signifigant problem? Does anyone > actually use this construct, and if so, for what? > > Brian In this case, it's simply the application that is not allowed as right-hand side of `let rec'. For instance, you can't do this : # let ( + ) a b = a :: b ;; val ( + ) : 'a -> 'a list -> 'a list = # let rec example = 1 + (2 + example) ;; This kind of expression is not allowed as right-hand side of `let rec' Let's remind that :: is a constructor of the type definition type 'a list = :: of 'a * 'a list | [] (even if we can't write it in a .ml file) If # let rec example = List.map (fun x -> x + 1) (1 :: 2 :: example);; were allowed, you would need lazy evaluation not to loop indefinitely. So if you really want to loop, you need to use let rec to define a function and not just a data. (meaning the data "can't loop" while functions can) Or like it has been suggested, you can use the module Lazy, but it's more job to do. Well, sometime it can be useful (though some find it ugly) to define recursive data structures such as this one (it's only a simple example) : # type 'a example = { mutable data : 'a list ; add : 'a -> unit ; } let create_example () = let rec e = { data = [] ; add = (fun x -> e.data <- x :: e.data); } in e ;; type 'a example = { mutable data : 'a list; add : 'a -> unit; } val create_example : unit -> 'a example = Then you can program like this : # let e = create_example ();; val e : '_a example = {data = []; add = } # let () = List.iter e.add [1; 2; 3; 4];; # let l = e.data ;; val l : int list = [4; 3; 2; 1] # e ;; - : int example = {data = [4; 3; 2; 1]; add = } Like this, you can, for instance, create a environment data structure with an abstraction barrier, as then you can define the abstract structure for the environment and the functions that handle it, while being able to change the list choice to a map or hash table choice and so on. Andrej Bauer wrote: > Brian Hurt wrote: >> Does anyone actually use this construct, and if so, for what? > > When I teach my students "theory" of programming languages, we write > interpreters for mini languages. The recursive data structures are > used to create closures of recursive functions, environments that > contain mutually recursive values, closures of objects, etc. Life > would be very hard without this feature. > > Andrej I don't think life would be very hard without this feature. (well, I mean I don't see any example that need this feature very badly) For recursive closures, for instance, the idea is to have something that looks like | RecClosure of name (* the name of the defined closure *) * name (* the first argument *) * expression (* i.e. the definition *) * environment Then if you need to evaluate an application, like | App of expression * expression So when you match an application with a recursive closure at the left-hand side... | App((ClosureRec (name, arg, def, env) as recclos), expr_b) -> let next_env = bind_var name recclos env in eval (bind_var x (eval higher_env expr_b) next_env) def Well, maybe it's quite inefficient compared to the use of a recursive data structure, I don't know, I haven't really thought about this question. But I mean I think it's not really hard to write an *interpreter* without "recursive data structure defined with let rec", until I'm showed an eloquent example :-p Regards, -- Philippe Wang