From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA22545 for caml-redistribution; Fri, 17 Sep 1999 13:12:48 +0200 (MET DST)
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 QAA28999 for <caml-list@pauillac.inria.fr>; Wed, 15 Sep 1999 16:37:43 +0200 (MET DST)
Received: from tequila.cs.yale.edu (TEQUILA.CS.YALE.EDU [128.36.229.152])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id QAA15707
	for <caml-list@inria.fr>; Wed, 15 Sep 1999 16:37:40 +0200 (MET DST)
Received: from tequila.cs.yale.edu (localhost [127.0.0.1])
	by tequila.cs.yale.edu (8.9.3/8.9.3) with SMTP id KAA16366
	for <caml-list@inria.fr>; Wed, 15 Sep 1999 10:37:35 -0400
To: caml-list@inria.fr
Sender: weis
From: "Stefan Monnier" <monnier+lists/caml/news/@tequila.cs.yale.edu>
Newsgroups: lists.caml
Subject: Re: Imperative list operations
References: <14302.41638.913957.615588@merlin.cs.clemson.edu>
Date: 15 Sep 1999 10:35:23 -0400
Message-ID: <5lzoyo8cpg.fsf@tequila.cs.yale.edu>
X-Newsreader: Gnus v5.7/Emacs 20.4
Path: tequila.cs.yale.edu
NNTP-Posting-Host: tequila.cs.yale.edu
X-Trace: 15 Sep 1999 10:35:23 -0500, tequila.cs.yale.edu

>>>>> "Steve" == Steve Stevenson <steve@cs.clemson.edu> writes:
> 	I need a double-ended queue implementation. The lists
> can get very long, so I would like to use imperative operations to
> change the links.

Since my O'Caml is very approximate, I'll answer with a non-answer:
have you tried a purely functional (but asymptotically efficient)
deque ?  Those don't suffer from the length of the queue.

Chris Okasaki has an interesting set of such purely functional data-structures,
with sample code in SML (and/or Haskell) which should be easy to translate to
O'Caml.  Check out, for example http://www.cs.columbia.edu/~cdo/jfp95/


	Stefan