* [Caml-list] Set and Map question @ 2004-09-20 2:37 Seth Fogarty 2004-09-20 3:14 ` [Caml-list] " Seth Fogarty 0 siblings, 1 reply; 10+ messages in thread From: Seth Fogarty @ 2004-09-20 2:37 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* [Caml-list] Re: Set and Map question 2004-09-20 2:37 [Caml-list] Set and Map question Seth Fogarty @ 2004-09-20 3:14 ` Seth Fogarty 2004-09-20 3:56 ` skaller 2004-09-20 4:02 ` Brian Hurt 0 siblings, 2 replies; 10+ messages in thread From: Seth Fogarty @ 2004-09-20 3:14 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 3:14 ` [Caml-list] " Seth Fogarty @ 2004-09-20 3:56 ` skaller 2004-09-20 4:18 ` Seth Fogarty 2004-09-20 4:02 ` Brian Hurt 1 sibling, 1 reply; 10+ messages in thread From: skaller @ 2004-09-20 3:56 UTC (permalink / raw) To: Seth Fogarty; +Cc: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 3:56 ` skaller @ 2004-09-20 4:18 ` Seth Fogarty 2004-09-20 6:43 ` skaller 2004-09-20 8:32 ` Diego Olivier Fernandez Pons 0 siblings, 2 replies; 10+ messages in thread From: Seth Fogarty @ 2004-09-20 4:18 UTC (permalink / raw) To: skaller; +Cc: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 4:18 ` Seth Fogarty @ 2004-09-20 6:43 ` skaller 2004-09-20 8:32 ` Diego Olivier Fernandez Pons 1 sibling, 0 replies; 10+ messages in thread From: skaller @ 2004-09-20 6:43 UTC (permalink / raw) To: Seth Fogarty; +Cc: caml-list, extlib 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 4:18 ` Seth Fogarty 2004-09-20 6:43 ` skaller @ 2004-09-20 8:32 ` Diego Olivier Fernandez Pons 1 sibling, 0 replies; 10+ messages in thread From: Diego Olivier Fernandez Pons @ 2004-09-20 8:32 UTC (permalink / raw) To: Seth Fogarty; +Cc: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 3:14 ` [Caml-list] " Seth Fogarty 2004-09-20 3:56 ` skaller @ 2004-09-20 4:02 ` Brian Hurt 2004-09-20 8:17 ` Richard Jones 1 sibling, 1 reply; 10+ messages in thread From: Brian Hurt @ 2004-09-20 4:02 UTC (permalink / raw) To: Seth Fogarty; +Cc: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 4:02 ` Brian Hurt @ 2004-09-20 8:17 ` Richard Jones 2004-09-20 12:41 ` Igor Pechtchanski 0 siblings, 1 reply; 10+ messages in thread From: Richard Jones @ 2004-09-20 8:17 UTC (permalink / raw) To: Brian Hurt; +Cc: caml-list [-- 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 --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 8:17 ` Richard Jones @ 2004-09-20 12:41 ` Igor Pechtchanski 2004-09-20 12:54 ` Jean-Christophe Filliatre 0 siblings, 1 reply; 10+ messages in thread From: Igor Pechtchanski @ 2004-09-20 12:41 UTC (permalink / raw) To: Richard Jones; +Cc: Brian Hurt, caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Re: Set and Map question 2004-09-20 12:41 ` Igor Pechtchanski @ 2004-09-20 12:54 ` Jean-Christophe Filliatre 0 siblings, 0 replies; 10+ messages in thread From: Jean-Christophe Filliatre @ 2004-09-20 12:54 UTC (permalink / raw) To: caml-list; +Cc: Richard Jones, Brian Hurt 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2004-09-20 12:54 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2004-09-20 2:37 [Caml-list] Set and Map question Seth Fogarty 2004-09-20 3:14 ` [Caml-list] " Seth Fogarty 2004-09-20 3:56 ` skaller 2004-09-20 4:18 ` Seth Fogarty 2004-09-20 6:43 ` skaller 2004-09-20 8:32 ` Diego Olivier Fernandez Pons 2004-09-20 4:02 ` Brian Hurt 2004-09-20 8:17 ` Richard Jones 2004-09-20 12:41 ` Igor Pechtchanski 2004-09-20 12:54 ` Jean-Christophe Filliatre
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).