CODEWITHSUNDEEP
f#
DotNetRussell
DotNetRussell

Reputation: 9857

Map in F# auto sorts but I don't know why

So when I do something like this

let mainMenu() = ["1. list item one",itemOne
                  "2. list item two",itemTwo
                  "3. list item three",itemThree
                  "4. list item four",itemFour
                  "0. Exit",exitApplication] 
                  |> Map.ofList

and print it like this

mainMenu() 
|> Seq.iter(fun keyValuePair -> 
    Console.WriteLine (sprintf "%s" (keyValuePair.Key |> string)))

I get a result of 

0. Exit
1. list item one
2. list item two
3. list item three
4. list item four

So my question is, how does it know to put 0 first in the list?

My assumption is that it's hashing the char 0 and that it's getting put into a bucket earlier on since it's ascii value is lower

Upvotes: 0

Views: 95

Answers (1)

sepp2k
sepp2k

Reputation: 370112

F#'s Maps are implemented using binary search trees (specifically AVL trees, I believe), not hash maps. Iterating a binary search tree depth-first gives you the items in sorted order.

Upvotes: 5

Related Questions