Re: [Caml-list] mutable lists

[Andreas Rossberg <rossberg@ps.uni-sb.de>]

Marco Maggesi wrote:
> 
> I noticed that OCaml do not have a library for mutable lists as, say,
> Lisp or Scheme where most procedure that operate on lists have both
> "functional" and "destructive" variants (like `append' and `append!').
> Is there any special theoretical reason for that?

Mainly that functional lists are considered nicer and much easier to use
(and thus more likely to be used right). Moreover, like all functional
data structures, they are persistent, ie. you can have multiple versions
of the same list or sublist simultanously.

> One more question about phantom types that are discussed in a parallel
> thread in these days.  Is it possible to use phantom types to prevent
> destructive operation on some lists?

Yes. For example, Matthias Blume's ML encoding of the C type system I
already mentioned in another post encodes C's constness annotations. The
basic idea is to have phantom types

	type ro (* read-only *)
	type rw (* read/write *)

and make your (mutable) list type polymorphic over them:

	type ('a,'r) list

Then you can specify operations in the signature as follows:

	val nil :      ('a,'r) list
	val cons :     'a -> ('a,'r) list  -> ('a,'r) list
	val length :   ('a,'r) list -> int
	val set_tail : ('a,rw) list -> ('a,rw) list -> unit
	val hash :     ('a,ro) list -> int

This prohibits destructively modifying the tail of a read-only list from
the outside as well as using a mutable list for hashing, while length
applies to any sort of list.

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr