Re: [Caml-list] How important are circular lists/recursive objects?

[Philippe Wang <lists@philippewang.info>]

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 = <fun>
# 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 = <fun>

Then you can program like this :

# let e = create_example ();;
val e : '_a example = {data = []; add = <fun>}
# 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 = <fun>}

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