From: skaller <skaller@us...>  20040823 20:04:24

On Tue, 20040824 at 05:04, Jesse Guardiani wrote: > On Monday 23 August 2004 2:45 pm, you wrote: > > > > On Aug 23, 2004, at 11:16, Jesse Guardiani wrote: > > > > > Yes, "deleting" would be. "Cutting" wouldn't. > > > > What is the difference between deleting and cutting? > > Deleting invalidates all nodes. Cutting doesn't invalidate any nodes > at all. > No. This is what the option backreference in the node type to the > list type is for. It insures that each node is associated with exactly > one list. It is not necessary to have the head pointer to ensure that: see below. > I'm growing weary of speculation. How about you guys actually look at > the code? Having a head pointer makes some operations O(N) instead of O(1). Here's the flavour I had in mind:  (* dlink soup *) type 'a node_t = { mutable data: 'a; mutable next: 'a node_t; mutable prev: 'a node_t; } (* invariant *) let check x = assert (x.prev.next = x); assert (x.next.prev = x) (* construction *) let singleton a = let rec x = { data=a; next=x; prev=x } in x (* accessor *) let get x = x.data (* special *) let is_tail x = x.next = x let is_head x = x.prev = x let is_singleton x = is_head x && is_tail x (* navigation *) let succ x = x.next let pred x = x.prev (* private utilities [break invariants] *) let link x y = x.next < y; y.prev < x let entail x = x.next < x let enhead x = x.prev < x (* chop a list in half *) let cut x = entail (pred x); enhead x (* remove one element from a list *) let del x = link (pred x) (succ x); link x x (* join tail x to head y *) let join x y = let xn = succ x and yp = pred y in link x y; xn.prev < xn; yp.next < yp (* swap the two tails *) let swap_tails x y = let yp = pred y in link (pred x) y; link yp x (* chop sublist, inclusive *) let chop h t = let hp = pred h and nt = succ t in cut h; cut nt; link hp nt  John Skaller, mailto:skaller@... voice: 061296600850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net 