From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA29891; Tue, 13 Aug 2002 18:12:07 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA29887 for <caml-list@pauillac.inria.fr>; Tue, 13 Aug 2002 18:12:06 +0200 (MET DST)
Received: from dewberry.cc.columbia.edu (dewberry.cc.columbia.edu [128.59.59.68])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g7DGC5L23429
	for <caml-list@inria.fr>; Tue, 13 Aug 2002 18:12:05 +0200 (MET DST)
Received: from there (tw304h3.cpmc.columbia.edu [156.111.84.180])
	by dewberry.cc.columbia.edu (8.9.3/8.9.3) with SMTP id MAA00208;
	Tue, 13 Aug 2002 12:11:56 -0400 (EDT)
Message-Id: <200208131611.MAA00208@dewberry.cc.columbia.edu>
Content-Type: text/plain;
  charset="iso-8859-1"
From: Oleg <oleg_inconnu@myrealbox.com>
To: "Anton Moscal" <msk@mail.tepkom.ru>
Subject: Re: [Caml-list] Doubly-linked list
Date: Tue, 13 Aug 2002 12:12:45 -0400
X-Mailer: KMail [version 1.3.2]
Cc: <caml-list@inria.fr>
References: <Pine.A32.3.95.1020813125617.63202A-100000@ibm1.cicrp.jussieu.fr> <200208131430.KAA23206@hickory.cc.columbia.edu> <012001c242db$ba4c9f90$2be213c3@youngkouzdra>
In-Reply-To: <012001c242db$ba4c9f90$2be213c3@youngkouzdra>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

On Tuesday 13 August 2002 11:11 am, Anton Moscal wrote:
> Hello, Oleg!
> You wrote to "Diego Olivier Fernandez Pons"
> <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr> on Tue, 13 Aug 2002
> 10:30:59 -0400:
>
>  O> Will it include imperative doubly-linked list or are all data types
>  O> going to
>  O> be purely functional? It's hard for me to think of an efficient
>  O> purely  functional doubly-linked list.
>
> For example:
>
> type 'a dll = 'a list (* before *) * 'a * 'a list (* next *)

I don't think this is a doubly-linked list.  In a doubly-linked listl, _each_ 
element contains "references" to the next and previous elements. In your dll 
type, there is only one such element.

Anyways, in O'Reilly book (and a verion posted to the list about two years 
ago), there is something similar to

type 'a dlist = {mutable prev : 'a dlist option; 
                     mutable next : 'a dlist option; 
                     info : 'a}

But I don't think it's very practically usable in its vanilla form. I 
wouldn't use a doubly-linked list implementation unles it provided
O(1) push_back, push_front, back, front, length (?), insert_before, 
insert_after, erase.

Maybe I'll write it in the next few days. What kind of bothers me is the need 
to have iterators (a la STL) as helper types.

Cheers
Oleg

> let ins_after elem (bef, cur, aft) = (cur::bef, elem, aft)
> let next = function (bef, cur, (cur'::aft)) -> Some ((cur::bef), cur', aft)
>
> | _ -> None
>
> let prev = function ((cur'::bef), cur, aft) -> Some (bef, cur', (cur::aft))
>
> | _ -> None
>
> ...
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners