[Caml-list] Set and Map question

[Caml-list] Set and Map question

[Seth Fogarty]

I am almost positive this has been addressed before, I just cannot
find it. Are map and fold over Set and Map garunteed to use an
in-order traversal?

-- 
Seth Fogarty             sfogarty@gmail.com
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

-------------------
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] Re: Set and Map question

[Seth Fogarty]

Beh, sorry, I was very confused and asked the wrong questions. The
answer to the below is yes, as specified in the manual, and I knew
that. Too many things juggling at once.

What I MEANT to ask is: Is there a O(n) method of set/map construction
from a list, as opposed to the O(n log n) fold method.


On Sun, 19 Sep 2004 21:37:15 -0500, Seth Fogarty <sfogarty@gmail.com> wrote:
> I am almost positive this has been addressed before, I just cannot
> find it. Are map and fold over Set and Map garunteed to use an
> in-order traversal?
> 
> --
> Seth Fogarty             sfogarty@gmail.com
> Neep-neep at large    AIM: Sorrath
> "I know there are people in this world who do not love their fellow
> human beings - and I hate people like that" --Tom Lehrer.
> 



-- 
Seth Fogarty             sfogarty@gmail.com
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

-------------------
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] Re: Set and Map question

[skaller]

On Mon, 2004-09-20 at 13:14, Seth Fogarty wrote:

> What I MEANT to ask is: Is there a O(n) method of set/map construction
> from a list, as opposed to the O(n log n) fold method.

It seems to me that in general that is impossible,
since random tree insertions are at least O(log n)
in the tree size (proportional to depth).

Perhaps you meant, assuming the list is sorted?
In that case, in theory you could precalculate
the shape of the tree just from the size, and then
fill in the elements in O(n).

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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] Re: Set and Map question

[Brian Hurt]

On Sun, 19 Sep 2004, Seth Fogarty wrote:

> Beh, sorry, I was very confused and asked the wrong questions. The
> answer to the below is yes, as specified in the manual, and I knew
> that. Too many things juggling at once.
> 
> What I MEANT to ask is: Is there a O(n) method of set/map construction
> from a list, as opposed to the O(n log n) fold method.

Implemented?  No.  Possible?  Yes, if the list is sorted.

The code is actually fairly easy.  Take the length of the list.  Subtract 
one for the root node.  The first (n-1)/2 elements are in the left hand 
subtree, the last n-1-((n-1)/2) elements are in the right subtree.

If the list isn't sorted, then no.  Any algorithm for turning the list 
into a sorted tree in less than O(N log N) would also serve for sorting 
the list in less than O(N log N), and would be a major advance in computer 
science.  I don't think it's possible, however.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
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] Re: Set and Map question

[Seth Fogarty]

Yes, sorry, sorted. I know it is possible, I was wondering if it was
implemented.


On 20 Sep 2004 13:56:10 +1000, skaller <skaller@users.sourceforge.net> wrote:
> On Mon, 2004-09-20 at 13:14, Seth Fogarty wrote:
> 
> > What I MEANT to ask is: Is there a O(n) method of set/map construction
> > from a list, as opposed to the O(n log n) fold method.
> 
> It seems to me that in general that is impossible,
> since random tree insertions are at least O(log n)
> in the tree size (proportional to depth).
> 
> Perhaps you meant, assuming the list is sorted?
> In that case, in theory you could precalculate
> the shape of the tree just from the size, and then
> fill in the elements in O(n).
> 
> --
> John Skaller, mailto:skaller@users.sf.net
> voice: 061-2-9660-0850,
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language http://felix.sf.net
> 
> 



-- 
Seth Fogarty             sfogarty@gmail.com
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

-------------------
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] Re: Set and Map question

[skaller]

On Mon, 2004-09-20 at 14:18, Seth Fogarty wrote:
> Yes, sorry, sorted. I know it is possible, I was wondering if it was
> implemented.

I'm not aware of it, but it seems like a very useful
function to have. 

I would guess there would be some interest
for the extlib project (I added a CC to that list)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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] Re: Set and Map question

[Richard Jones]

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

On Sun, Sep 19, 2004 at 11:02:44PM -0500, Brian Hurt wrote:
> The code is actually fairly easy.  Take the length of the list.  Subtract 
> one for the root node.  The first (n-1)/2 elements are in the left hand 
> subtree, the last n-1-((n-1)/2) elements are in the right subtree.

Wouldn't you have to iterate over the list when implementing this?
What I mean to say is that this would work if you had a pre-sorted
Array, but not a linked List.  ?

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
http://www.winwinsales.co.uk/ - CRM improvement consultancy

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] Re: Set and Map question

[Diego Olivier Fernandez Pons]

    Bonjour,

> Yes, sorry, sorted. I know it is possible, I was wondering if it was
> implemented.

I never understood how worked those functions building a balanced
search tree from a sorted list in O(n) _without_ first counting the
number of elements in the list.

Hence it is not implemented in Baire. As far as I know, there is no
Caml implementation of any of them either (they all iter on the list
applying O(log n) insertion function) but I may be wrong.

SML/NJ standard library has a O(n) 'from_ordered_list' function for
red-black trees. SML/NJ implementation of red-black trees uses zippers
to handle insertion and deletion operations. It may be difficult to
understand if you are not used to them.

Ralf Hinze wrote a good paper on red-black trees (Constructing
red-black trees, WAAAPL'99, available from his website). It explains
how to implement 'from_ordered_list' in O(n) and most of existent
functional implementations must be more or less based on it.


        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] Re: Set and Map question

[Igor Pechtchanski]

On Mon, 20 Sep 2004, Richard Jones wrote:

> On Sun, Sep 19, 2004 at 11:02:44PM -0500, Brian Hurt wrote:
> > The code is actually fairly easy.  Take the length of the list.  Subtract
> > one for the root node.  The first (n-1)/2 elements are in the left hand
> > subtree, the last n-1-((n-1)/2) elements are in the right subtree.
>
> Wouldn't you have to iterate over the list when implementing this?
> What I mean to say is that this would work if you had a pre-sorted
> Array, but not a linked List.  ?

Did the question mention anything about the space used by the algorithm?
If one is allowed O(n) temp space, then simply converting the sorted
linked List into a temp array as the first step will keep the algorithm
O(n) (constant factors aside).  One would need a constant-time-access data
structure anyway, to build a balanced tree bottom-up in a functional way.
	Igor
-- 
				http://cs.nyu.edu/~pechtcha/
      |\      _,,,---,,_		pechtcha@cs.nyu.edu
ZZZzz /,`.-'`'    -.  ;-;;,_		igor@watson.ibm.com
     |,4-  ) )-,_. ,\ (  `'-'		Igor Pechtchanski, Ph.D.
    '---''(_/--'  `-'\_) fL	a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

"Happiness lies in being privileged to work hard for long hours in doing
whatever you think is worth doing."  -- Dr. Jubal Harshaw

-------------------
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] Re: Set and Map question

[Jean-Christophe Filliatre]

Igor Pechtchanski writes:
 > On Mon, 20 Sep 2004, Richard Jones wrote:
 > 
 > > On Sun, Sep 19, 2004 at 11:02:44PM -0500, Brian Hurt wrote:
 > > > The code is actually fairly easy.  Take the length of the list.  Subtract
 > > > one for the root node.  The first (n-1)/2 elements are in the left hand
 > > > subtree, the last n-1-((n-1)/2) elements are in the right subtree.
 > >
 > > Wouldn't you have to iterate over the list when implementing this?
 > > What I mean to say is that this would work if you had a pre-sorted
 > > Array, but not a linked List.  ?
 > 
 > Did the question mention anything about the space used by the algorithm?
 > If one is allowed O(n) temp space, then simply converting the sorted
 > linked List into a temp array as the first step will keep the algorithm
 > O(n) (constant factors aside).  One would need a constant-time-access data

There is no need converting the list into an array. Once the length is
computed (with a single traversal of the list), it is possible to
build the tree with only another traversal of the list. Here is for
instance how to build a red-black tree from a (reverse) sorted list of
elements:

===========================================================================
  (*s Building a red-black tree from a sorted list in reverse order.
      The result is a complete binary tree, where all nodes are black, 
      except the bottom line which is red.  *)

  let log2 n = truncate (log (float n) /. log 2.)

  let of_list sl = 
    let rec build sl n k =
      if k = 0 then
	if n = 0 then 
	  Empty, sl 
	else match sl with
	  | [] -> 
	      assert false
	  | x :: sl  -> 
	      Red (Empty, x, Empty), sl
      else
	let n' = (n - 1) / 2 in
	match build sl n' (k - 1) with
	  | _, [] -> 
	      assert false
	  | l, x :: sl -> 
	      let r, sl = build sl (n - n' - 1) (k - 1) in
	      Black (r, x, l), sl
    in
    let n = List.length sl in
    fst (build sl n (log2 n))
===========================================================================

The key idea is to return the tree together with the list of unused
elements in the list. 

regards,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

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