tags:

views:

76

answers:

2
+1  Q: 

Is an iteration on a F# map or set in-order traversal?

AFAIK, F# Map and set are implemented as red-black trees, so I guess that an iteration on these would be in-order traversal. I did some test and the iteration results are always sorted. But I want to make it sure.

Is it in-order traversal?

+3  A: 

The documentation on MSDN is pretty good for figuring this out. For instance, the return value for Set.toSeq is "An ordered sequence of the elements of set." It looks like the answer to your question is yes, for both maps and sets.

kvb  2010-06-04 21:26:46
Oh, thnx, I am silly. I was looking up the document of the Map Class only, not the Map Module.
tk  2010-06-04 21:36:33
A: 

AFAIK, F# Map and set are implemented as red-black trees

AVL trees.

Is it in-order traversal?

Yes.

Jon Harrop  2010-06-05 10:53:49

related questions

iterative version of easy recursive algorithm
Existing LINQ extension method similar to Parallel.For?
How to modify or delete items from an enumerable collection while iterating through it in C#
modern for loop for primitive array
Converting a List of Tuples into a Dict in Python
iterative version of recursive algorithm to make a binary tree
Why is it bad to use a iteration variable in a lambda expression
What is the easiest/best/most correct way to iterate through the characters of a string in Java?
Is Iterator initialization inside for loop considered bad style, and why?
.NET Fastest way to iterate through rows in a datatable?
Way to go from recursion to iteration
Team size and project iteration length.
Is it correct to use the backtick / comma idiom inside a (loop ...)?
Is there a zip-like method in .Net?
How do I iterate a .Net IList collection in the reverse order?
In C# .NET 2.0, what's an easy way to do a foreach in reverse?
Iterators in C++ (stl) vs Java, is there a conceptual difference?
Iterate Over Map
Lisp list iteration
Why does Python's iter() on a mapping return iterkeys() instead of iteritems()?
Replacement for for... if array iteration
Generic iterator
What's the safest way to iterate through the keys of a Perl hash?
How do I use Python's itertools.groupby()?
Using 'in' to match an attribute of Python objects in an array