[Caml-list] mutable lists

[Caml-list] mutable lists

[Marco Maggesi]

Hi,

I am learning OCaml.  I would like to ask some questions.

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?

Anyway, I am writing one such library for mutable lists as excuse for
me to learn OCaml and play with it.  It is freely available from
  http://www.math.unifi.it/~maggesi/srfi/
It is inspired from the Olin Shiver code for the SRFI-1 "List library"
for scheme (http://srfi.schemers.org/srfi-1/srfi-1.html).  Comments
are really welcomed.

Are there already other libraries for mutable lists available in
OCaml?  So that I can learn by comparison.

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?

Thanks for your patient with beginners,
Marco
-------------------
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

Re: [Caml-list] mutable lists

[Andreas Rossberg]

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