[Caml-list] Doubly-linked list

[Caml-list] Doubly-linked list

[Oleg]

Hi

Has anyone implemented a doubly-linked list with O(1) push_back, push_front, 
back, front, length operations?

Thanks
Oleg

P.S. BTW, one could have identical interfaces for a) resizable arrays, b) 
doubly-linked lists and c) deques, the only difference being the efficiency 
of various operations. It could be convenient for a programmer, because final 
data representation can be chosen after the program has been profiled and 
without changing much code. Has anyone tackled this problem?
-------------------
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

Re: [Caml-list] Doubly-linked list

[Markus Mottl]

On Tue, 13 Aug 2002, Oleg wrote:
> P.S. BTW, one could have identical interfaces for a) resizable arrays

In case you need it, this is the case with my RES-library, which offers
resizable arrays, strings and weak arrays with compatible interfaces:

  http://www.ai.univie.ac.at/~markus/home/ocaml_sources.html

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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

Re: [Caml-list] Doubly-linked list

[Diego Olivier Fernandez Pons]

Oleg a écrit :

> P.S. BTW, one could have identical interfaces for a) resizable arrays, b) 
> doubly-linked lists and c) deques, the only difference being the efficiency 
> of various operations. It could be convenient for a programmer, because final 
> data representation can be chosen after the program has been profiled and 
> without changing much code. Has anyone tackled this problem?

I will be soon releasing a data structure library (september) which
includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), all
data structures that were in Okasaki's purely functional data
structures book and some more (weight balanced trees, cartesian trees,
priority search queues, ...)

It uses an uniform data representation for the programmer to chose
after the program has been profiled and without changing much code.

        Diego Olivier

-------------------
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

Re: [Caml-list] Doubly-linked list

[Oleg]

On Tuesday 13 August 2002 07:00 am, Diego Olivier Fernandez Pons wrote:
> I will be soon releasing a data structure library (september) which
> includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), all
> data structures that were in Okasaki's purely functional data
> structures book and some more (weight balanced trees, cartesian trees,
> priority search queues, ...)
>
> It uses an uniform data representation for the programmer to chose
> after the program has been profiled and without changing much code.

Will it include imperative doubly-linked list or are all data types going to 
be purely functional? It's hard for me to think of an efficient purely 
functional doubly-linked list.

Regards,
Oleg
-------------------
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

Re: [Caml-list] Doubly-linked list

[Anton Moscal]

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 *)

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
...

Anton Moscal.
-------------------
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

Re: [Caml-list] Doubly-linked list

[Oleg]

On Tuesday 13 August 2002 04:54 am, Markus Mottl wrote:
> On Tue, 13 Aug 2002, Oleg wrote:
> > P.S. BTW, one could have identical interfaces for a) resizable arrays
>
> In case you need it, this is the case with my RES-library, which offers
> resizable arrays, strings and weak arrays with compatible interfaces:
>
>   http://www.ai.univie.ac.at/~markus/home/ocaml_sources.html

I am using Res.Array actually.

Regards
Oleg
-------------------
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

Re: [Caml-list] Doubly-linked list

[Oleg]

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

Re: [Caml-list] Doubly-linked list

[Brian Rogoff]

Diego Olivier Fernandez Pons writes:
> Oleg a écrit :
> 
> > P.S. BTW, one could have identical interfaces for a) resizable arrays, b) 
> > doubly-linked lists and c) deques, the only difference being the efficiency 
> > of various operations. It could be convenient for a programmer, because final 
> > data representation can be chosen after the program has been profiled and 
> > without changing much code. Has anyone tackled this problem?
> 
> I will be soon releasing a data structure library (september) which
> includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), all
> data structures that were in Okasaki's purely functional data
> structures book and some more (weight balanced trees, cartesian trees,
> priority search queues, ...)

I'm looking forward to seeing it. I get the impression that Edison uses 
(multi-parameter) type classes so it isn't clear that it will translate 
well. Oh yeah, I may as well add my biannual plea for some form of
overloading in OCaml, which is somewhere in the top 3 of my wishlist. 

Anyways, doubly linked lists are a textbook example of an imperative data 
structure, and, waddya know, a very good textbook (the Cousineau/Mauny one
which is owned by everyone on this list ;-) has this example pretty early
in the section on imperative programming. Look here for the source 

http://pauillac.inria.fr/cousineau-mauny/main.html

but realize that you'll have to translate the source into OCaml. If I
remember correctly, the doubly linked list looks something like 

type 'a t = 
  { data : 'a; 
    mutable prev : 'a t; 
    mutable next : 'a t
  }

let create e = let rec x = {data = e; prev = x; next = x} in x

etc. 

which is very nice if you are used to trying such things in SML. 

-- Brian
-------------------
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

Re: [Caml-list] Doubly-linked list

[Max Kirillov]

[-- Attachment #1: Type: text/plain, Size: 477 bytes --]

On Tue, Aug 13, 2002 at 12:12:45PM -0400, Oleg wrote:
> type 'a dlist = {mutable prev : 'a dlist option; 
>                      mutable next : 'a dlist option; 
>                      info : 'a}


> 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.

Unless you need thread-safe behavior, that could be just
"'a dlist ref". I tried to do some fast things. See
attachment.  That's just an idea.

Max.

[-- Attachment #2: dlist.ml --]
[-- Type: text/plain, Size: 1047 bytes --]


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

type 'a dlist = {mutable front: 'a t;
		mutable back: 'a t}

exception Bound

next = function {next=Some obj1} -> obj1 | _ -> raise Bound
prev = function {prev=Some obj1} -> obj1 | _ -> raise Bound

takeNext objR = objR:=(next !objR)
takePrev objR = objR:=(prev !objR)

add_before v obj =
	let newObj = {prev=None;next=obj;info=v} in
	(match obj
	    with {prev=Some obj1} -> (newObj.prev<-obj1;
				    obj1.next<-newObj)
		| {prev=None} -> ());
	obj.prev=newObj
	    
add_after v obj =
	let newObj = {next=None;prev=obj;info=v} in
	(match obj
	    with {next=Some obj1} -> (newObj.next<-obj1;
				    obj1.prev<-newObj)
		| {next=None} -> ());
	obj.next=newObj

(* Hmm... I'm not clear whether front is after back or before it.
    Depends on moving direction:) Let's suppose before *)

push_back v ({back=obj} as data) = add_after v obj; data.back <- next obj
push_front v ({front=obj} as data) = add_before v obj; data.front <- prev obj

Re: [Caml-list] Doubly-linked list

[Anton E. Moscal]

13 Aug 2002 20:12, Oleg wrote:

> >  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}

This isn't "purely functional" :)
>
> 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.

insert_before, erase (AKA empty), length in my representation are 
straightforward. push_back, push_front etc are more complex, but probably - 
asymtotically O(1). 

Really, my solution is a variarion on theme of the purely functional queue 
which can be found in Okasaki (or surprisingly - in the Gries "Science of 
programming" :) )

Anton
-------------------
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

Re: [Caml-list] Doubly-linked list

[Max Kirillov]

[-- Attachment #1: Type: text/plain, Size: 125 bytes --]

I should stop sitting after 24. At least don't send
anything. It's full of errors.
It's not an ocaml at all...

Sorry.

Max.

[-- Attachment #2: dlist.ml --]
[-- Type: text/plain, Size: 1121 bytes --]


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

type 'a dlist = {mutable front: 'a t;
		mutable back: 'a t}

exception Bound

let next = function {next=Some obj1} -> obj1 | _ -> raise Bound
let prev = function {prev=Some obj1} -> obj1 | _ -> raise Bound

let takeNext objR = objR:=(next !objR)
let takePrev objR = objR:=(prev !objR)

let add_before v obj =
	let newObj = {prev=None;next=Some obj;info=v} in
	(match obj
	    with {prev=Some obj1} -> (newObj.prev<-Some obj1;
				    obj1.next<-Some newObj)
		| {prev=None} -> ());
	obj.prev<-Some newObj
	    
let add_after v obj =
	let newObj = {next=None;prev=Some obj;info=v} in
	(match obj
	    with {next=Some obj1} -> (newObj.next<-Some obj1;
				    obj1.prev<-Some newObj)
		| {next=None} -> ());
	obj.next<-Some newObj

(* Hmm... I'm not clear whether front is after back or before it.
    Depends on moving direction:) Let's suppose before *)

let push_back v ({back=obj} as data) = add_after v obj; data.back <- next obj
let push_front v ({front=obj} as data) = add_before v obj; data.front <- prev obj

Re: [Caml-list] Doubly-linked list

[Diego Olivier Fernandez Pons]

Brian Rogoff a écrit

> > I will be soon releasing a data structure library (september) which
> > includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), all
> > data structures that were in Okasaki's purely functional data
> > structures book and some more (weight balanced trees, cartesian trees,
> > priority search queues, ...)
> 
> I'm looking forward to seeing it. I get the impression that Edison uses 
> (multi-parameter) type classes so it isn't clear that it will translate 
> well. Oh yeah, I may as well add my biannual plea for some form of
> overloading in OCaml, which is somewhere in the top 3 of my wishlist. 

I had to make many changes to Edison's structure including :

- flattening the Haskell class hierarchy
  Edison has Coll, XColl, OrdColl, Set, XSet, OrdSet ... you can see a
  few diagrammas (in fact lattices) in Okasaki's overviews of Edison.
  They have been all reduced into 4 types (Sequences, Collections,
  Sets and Maps) in various flavors (polymorphic, functor, in place)

- transforming some lazy data structures to strict (and providing
  functors and various flavors of streams for those who want amortized
  data structures via lazy evaluation)

- eliminating data structures that could not be translated to Caml,
  which includes some multi-parameter classes (that was not the most
  difficult part in fact) and non-uniform recursion (most of the last
  3 chapters of Okasaki's book, Markus Mottle had the same problem
  with his translation to Caml)

There won't be much new if you already use Markus Mottle port :
- weight balanced trees (Stephen Adams 1992)
- cartesian trees (Jean Vuillemin 1980)
- catenable (functional) lists (Chris Okasaki 1998)
- chromatic trees (Sabine Hanke 1997)
- priority search queues (Ralph Hinze 2001)
- various flavors of streams
- some mutable lists
- I have also completed Pottier's simply linked circular lists


        Diego Olivier

-------------------
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

Re: [Caml-list] Doubly-linked list

[Brian Rogoff]

Diego Olivier Fernandez Pons writes:
> Brian Rogoff a écrit
> > I'm looking forward to seeing it. I get the impression that Edison uses 
> > (multi-parameter) type classes so it isn't clear that it will translate 
                          ^-constructor
> > well. Oh yeah, I may as well add my biannual plea for some form of
> > overloading in OCaml, which is somewhere in the top 3 of my wishlist. 
> 
> I had to make many changes to Edison's structure including :
> 
> - flattening the Haskell class hierarchy
>   Edison has Coll, XColl, OrdColl, Set, XSet, OrdSet ... you can see a
>   few diagrammas (in fact lattices) in Okasaki's overviews of Edison.
>   They have been all reduced into 4 types (Sequences, Collections,
>   Sets and Maps) in various flavors (polymorphic, functor, in place)
> 
> - transforming some lazy data structures to strict (and providing
>   functors and various flavors of streams for those who want amortized
>   data structures via lazy evaluation)
> 
> - eliminating data structures that could not be translated to Caml,
>   which includes some multi-parameter classes (that was not the most
>   difficult part in fact) 

Yes, you can always map to modules, but I think overloading (or type
classes, if you want to distinguish from Ada and C++) are more convenient
for the user, but I suppose this is a well known disagreement that will
only be resolved by the proponents of the respective positions choosing
different languages. 

> and non-uniform recursion (most of the last
>   3 chapters of Okasaki's book, Markus Mottle had the same problem
>   with his translation to Caml)

With OCaml 3.05 and above, you'll be able to use polymorphic methods to 
get non-uniform recursion. This issue has come up a lot on the list 
(see the archives) over the years and several proposals were made for 
adding this capability to the language. I don't know if adding this 
feature is a priority for the developers; it isn't clear that the data
structures in Okasaki's book constitute a strong enough argument for 
adding it. 

You may as well swipe the doubly linked list from the Cousineau/Mauny book
too. The library will be more useful if you're very careful about making
the interfaces very consistent, so that changing a data structure doesn't
cause much source code change. 
> 
> There won't be much new if you already use Markus Mottle port :
> - weight balanced trees (Stephen Adams 1992)
> - cartesian trees (Jean Vuillemin 1980)
> - catenable (functional) lists (Chris Okasaki 1998)
> - chromatic trees (Sabine Hanke 1997)
> - priority search queues (Ralph Hinze 2001)
> - various flavors of streams
> - some mutable lists
> - I have also completed Pottier's simply linked circular lists
> 
> 
>         Diego Olivier

-- Brian
-------------------
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

Re: [Caml-list] Doubly-linked list

[Diego Olivier Fernandez Pons]

Brian Rogoff a écrit :

> With OCaml 3.05 and above, you'll be able to use polymorphic methods to 
> get non-uniform recursion. This issue has come up a lot on the list 
> (see the archives) over the years and several proposals were made for 
> adding this capability to the language. I don't know if adding this 
> feature is a priority for the developers; it isn't clear that the data
> structures in Okasaki's book constitute a strong enough argument for 
> adding it. 

Non-uniform recursion allows you to capture structure invariants in
your type, which means that the correction of the algorithms will not
be proved by the programmer but by the type-checker. 

I think it is a big improvment. Chris Okasaki's data structure may not
be a strong enough argument, but more complicated data structures are
being studied.

You can find some (simple) examples in a paper by Ralf Hinze
"Manufacturing data types", namely braun trees, 2-3 trees, matrices 


Concerning double linked lists, for the moment I am working on things
I think are more important.

        Diego Olivier

-------------------
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

Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[Brian Rogoff]

Diego Olivier Fernandez Pons writes:
> Brian Rogoff a écrit :
> > With OCaml 3.05 and above, you'll be able to use polymorphic methods to 
> > get non-uniform recursion. This issue has come up a lot on the list 
> > (see the archives) over the years and several proposals were made for 
> > adding this capability to the language. I don't know if adding this 
> > feature is a priority for the developers; it isn't clear that the data
> > structures in Okasaki's book constitute a strong enough argument for 
> > adding it. 
> 
> Non-uniform recursion allows you to capture structure invariants in
> your type, which means that the correction of the algorithms will not
> be proved by the programmer but by the type-checker. 

Oh I'm not arguing that point, I totally agree that it's omission is a 
bad thing. However, not everyone agrees, since you it becomes a lot tougher
to build a monomorphizing compiler if you allow it, though it has been 
suggested that the same tricks you use to manually remove polymorphic
recursion could be used in an SSC (sufficiently smart compiler). 

Anyways, since OCaml 3.05 allows first class polymorphism on records, you
don't even need to use "polymorphic recots" to get non-uniform recursion; 
simply mapping the OOP to records does the trick. Here's the first example
from OKasaki which uses polymorphic recursion, done in OCaml with this 
direct approach 

module type RANDOM_ACCESS_LIST =
  sig
    type 'a ra_list

    val empty   : 'a ra_list
    val is_empty : 'a ra_list -> bool

    val cons    : 'a -> 'a ra_list -> 'a ra_list
    val head    : 'a ra_list -> 'a
    val tail    : 'a ra_list -> 'a ra_list
    val lookup  : int -> 'a ra_list -> 'a
    val update  : int -> 'a -> 'a ra_list -> 'a ra_list
  end

module AltBinaryRandomAccessList : RANDOM_ACCESS_LIST =
  (* assumes polymorphic recursion! *)
  struct 
    type 'a ra_list = Nil
    | Zero of ('a * 'a) ra_list
    | One of 'a * ('a * 'a) ra_list

    let empty = Nil
    let is_empty = function Nil -> true | _ -> false

    (* Use first class polymorphism to get the effect of explicitly typing 
       the polymorphic recursion 
    *)
    type dictionary = 
      { cons : 'a. dictionary -> 'a -> 'a ra_list -> 'a ra_list;
	uncons : 'a. dictionary -> 'a ra_list -> 'a * 'a ra_list;
	lookup : 'a. dictionary -> int -> 'a ra_list -> 'a;
	fupdate : 'a. dictionary -> ('a -> 'a) -> int -> 'a ra_list -> 'a 
ra_list
      }

    (* Define the methods, taking care that the recursive calls go through
       the dictionary
    *)

    let cons' dict x l =
      match l with
	Nil -> One (x, Nil)
      | Zero ps -> One (x, ps)
      | One (y,b) -> Zero (dict.cons dict (x, y) b)

    let uncons' dict l =
      match l with
	Nil -> raise Not_found
      | One (x,Nil) -> (x,Nil)
      | One (x,ps) -> (x, Zero ps)
      | Zero ps -> 
	  let ((x,y),ps') = dict.uncons dict ps in 
	  (x, One (y, ps'))

    let lookup' dict i l = 
      match i,l with 
	(i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> x
      | (i, One (x, ps)) -> dict.lookup dict (pred i) (Zero ps)
      | (i, Zero ps) -> 
	  let (x, y) = dict.lookup dict (i / 2) ps
	  in if i mod 2 = 0 then x else y

    let rec fupdate' dict f i l =
      match i,l with 
	(i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> One (f x, ps)
      | (i, One (x, ps)) -> dict.cons dict x (dict.fupdate dict f (i-1) (Zero 
ps))
      | (i, Zero ps) ->
	  let f' (x, y) = if i mod 2 = 0 then (f x, y) else (x, f y) in 
	  Zero (dict.fupdate dict f' (i / 2) ps)


    (* Make the sole dictionary which will be called *)

    let methods = 
      { cons = cons'; uncons = uncons'; lookup = lookup'; fupdate = fupdate' }

    (* Make the actual functions *)
    let cons x l = cons' methods x l 
    let uncons l = uncons' methods l 
    let head xs = let (x, _) = uncons xs in x
    let tail xs = let (_, xs') = uncons xs in xs'
    let lookup i xs = lookup' methods i xs
    let update i y xs = fupdate' methods (fun x -> y) i xs
  end

> I think it is a big improvment. Chris Okasaki's data structure may not
> be a strong enough argument, but more complicated data structures are
> being studied.

I agree, and I hope that in the future we won't have to use hacks like the 
above to get polymorphic recursion, but that it will be supported more
directly. The style above, besides being indirect, is also a little uglier
still when you're using the tail recursive accumulator passing style
because your recursive functions have funny names and signatures. In any
case, this kind of hack will allow you to translate these structures and
won't require much rework when polymorphic recursion is finally added 
"for real"

-- Brian
-------------------
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

Re: [Caml-list] Doubly-linked list

[james woodyatt]

On Tuesday, Aug 13, 2002, at 01:00 US/Pacific, Oleg wrote:
>
> Has anyone implemented a doubly-linked list with O(1) push_back, 
> push_front,
> back, front, length operations?
>
> Thanks
> Oleg
>
> P.S. BTW, one could have identical interfaces for a) resizable arrays, 
> b)
> doubly-linked lists and c) deques, the only difference being the 
> efficiency
> of various operations. It could be convenient for a programmer, 
> because final
> data representation can be chosen after the program has been profiled 
> and
> without changing much code. Has anyone tackled this problem?

I have recently been working on a fully-persistent, catenable deque 
that uses explicit recursive slowdown , á la Kaplan and Tarjan, to 
achieve what seems to me to be O(1) amortized cost for all the 
traditional operations.  I think my design may be substantially simpler 
than algorithms I've seen published to date, but I'm not sure.  I'm 
certain it isn't O(1) for all operations, but I can push and shift 
millions of objects into and out of a deque without any noticeable 
degradation in performance over the size of a deque.  In other words, 
it looks to me to be good enough for government work.

When I've put the code through some more paces, I will publish it.  
Give me a few more weeks.


--james

-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[Diego Olivier Fernandez Pons]

Brian Rogoff a écrit

> Oh I'm not arguing that point, I totally agree that it's omission is a 
> bad thing. However, not everyone agrees, since you it becomes a lot tougher
> to build a monomorphizing compiler if you allow it, though it has been 
> suggested that the same tricks you use to manually remove polymorphic
> recursion could be used in an SSC (sufficiently smart compiler). 

I do not agree with your analysis since I really do not believe anyone
could think that polymorphic recursion is useless. But it is a
_difficult_ subject and the Caml Team is working on it (you can read
their research summary)

Actually, I do not even think that including some tricks in the
compiler is a manageable solution.

> Anyways, since OCaml 3.05 allows first class polymorphism on records, you
> don't even need to use "polymorphic recots" to get non-uniform recursion; 
> simply mapping the OOP to records does the trick. Here's the first example
> from OKasaki which uses polymorphic recursion, done in OCaml with this 
> direct approach 

[...]

Your trick is very interesting but I am afraid I cannot include that
kind of code in a library whose purpose is also to be a pedagogical
support for a data structure course in Caml and an example for
beginners (maybe released as independent modules ?)

        Diego Olivier

-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[Brian Rogoff]

Diego Olivier Fernandez Pons writes:
> I do not agree with your analysis since I really do not believe anyone
> could think that polymorphic recursion is useless. 

Every feature in a programming language has to be evaluated in a large 
context. There are lot's of useful features that OCaml doesn't have. Would
you add them all? 

I never said polymorphic recursion was useless, and I'd like direct support
for it added, so your claim that my analysis suggests it's uselessness
indicates that I am communicating very badly. I'll just be quiet on this 
topic. 

> Your trick 

Actually, Jacques Garrigue's trick

http://caml.inria.fr/archives/199809/msg00032.html

but I just noticed that OCaml 3.05 has the same first class polymorphism on 
records and since there was no use of class features like dynamic binding
that a record dictionary is even better. 

BTW, the Caml mailing list archive is a really great resource. 

-- Brian
-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[Diego Olivier Fernandez Pons]

On Wed, 21 Aug 2002, Brian Rogoff wrote:

> I never said polymorphic recursion was useless, and I'd like direct support
> for it added, so your claim that my analysis suggests it's uselessness
> indicates that I am communicating very badly. I'll just be quiet on this 
> topic. 

Sorry, I misundestood what you were saying. I did'n meant to offend
you.

    Diego Olivier

-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[John Max Skaller]

Diego Olivier Fernandez Pons wrote:

> Brian Rogoff a écrit
> 
> 
>>Oh I'm not arguing that point, I totally agree that it's omission is a 
>>bad thing. However, not everyone agrees, since you it becomes a lot tougher
>>to build a monomorphizing compiler if you allow it, though it has been 
>>suggested that the same tricks you use to manually remove polymorphic
>>recursion could be used in an SSC (sufficiently smart compiler). 
>>
> 
> I do not agree with your analysis since I really do not believe anyone
> could think that polymorphic recursion is useless. But it is a
> _difficult_ subject and the Caml Team is working on it (you can read
> their research summary)


I'm confused. I think you mean *type inference* is difficult
if you want polymorphic recursion?

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[Diego Olivier Fernandez Pons]

John Max Skaller a écrit :

> I'm confused. I think you mean *type inference* is difficult
> if you want polymorphic recursion?

I'am confused too. We do want type inference, do we not ? And
polymorphic recursion makes type inference undecidable. 

- Haskell allows full polymorphic recursion but requires providing
explicitly a type signature (in fact, in Haskell you always provide
type annotations even if it is not required)

- Caml now allows a restricted kind of polymorphic recursion but keeps
most of the type inference (there were a few constructions in Caml
which already required type annotations, I don't know yet how
polymorphic methods interfer with type inference, I suppose the Caml
team can answer that question) 


        Diego Olivier

-------------------
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

Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[John Max Skaller]

Diego Olivier Fernandez Pons wrote:

> John Max Skaller a écrit :
> 
> 
>>I'm confused. I think you mean *type inference* is difficult
>>if you want polymorphic recursion?
>>
> 
> I'am confused too. We do want type inference, do we not ? And
> polymorphic recursion makes type inference undecidable. 


I thought type inference was already of such worst case
complexity that it is effectively equivalent to undecidable :-)
In practice, this is rarely a problem I believe.

In any case, I'd rather more generality than a guarrantee of
type inference: annotating function arguments when necessary
isn't that onerous is it?

> - Haskell allows full polymorphic recursion but requires providing
> explicitly a type signature (in fact, in Haskell you always provide
> type annotations even if it is not required)


Felix requires annotation too, because it also provides overloading
(and therefore it is often necessary). This definitely
makes function signatures more difficult to write, but it
allows more intuitive calling.

Felix is lower order (less emphasis on higher order things)
than Ocaml, so it is surprising that these higher order things
are actually *easier* to support in the compiler
(bottom up deduction is efficient, but it gets quite nasty
with overloading added in .. sometimes return types
have to be declared too)

It seems the advantages of full inference lessen both
as one tries for a lower order language (like Felix)
or a higher order language (like Haskell): inference
is maximally useful 'in between'. Most Ocaml programs
do live 'in between', but there is another fact:
annotating functions 'in between' is not much of a burden.

So we gain most advantage from type inference for

a small class of functions whose types are moderately
complex: those of less complexity are easy to annotate,
and those of more complexity cannot be easily annotated
OR computed.

I wonder if it is possible to find out how popular
this class of functions is in actual usage?

Can we see some cases where inference provides

a definitive advantage? [I have seen some before ..
they certainly exist]


-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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

[Caml-list] FELIX (was: Polymorphic recursion)

[Oleg]

On Wednesday 28 August 2002 10:50 am, John Max Skaller wrote:
> Felix [...]

How is Felix doing BTW? Does it have plans for world domination?

Oleg
-------------------
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