We are running some ElixirCard challenges at CodeElixir LDN this year, and thought it would be fun to post them here on the forum too.
What would the following return?
list = [a: 1, b: 2]
[{"foo", "bar"} | list]
The solution, along with some further information will be posted tomorrow 
Well… in IEX I get…
[{"foo", "bar"}, {:a, 1}, {:b, 2}]
I shall let you explain why tomorrow! 
Somebody should make a twitter bot that holds an ElixirCard competition.
Twitter bot sounds like a great idea!
…and now for the explanation 
list = [a: 1, b: 2]
# what will this return
[{"foo", "bar"} | list]
[{"foo", "bar"}, {:a, 1}, {:b, 2}]
When a list in Elixir contains tuples, where the first element is an atom and the second element is a value of any term, it is considered a keyword list. Keyword lists have a special visual representation, and the square brackets can be omitted if the keyword list is the last argument of a function or macro call, or is the last element in a tuple.
That might sound kinda odd and rather convoluted, but there is rhyme and reason.
For instance when adding a dependency to the list of dependencies in a project mix-file, it is usually done as a two tuple; first element consisting of the identifier for the dependency as an atom, the second element being the requested version.
{:ex_doc, "~> 0.19"}
When we need to specify options for a dependency we can do so by using a three tuple instead; and here we use a list with our options. In the case of ExDoc we do not need it during our applications runtime, and we would not like it to be part of anything but the development environment. We can inform the system of these requirements by passing in our keyword list like this:
{:ex_doc, "~> 0.19", [{:only, :dev}, {:runtime, false}]}
Because the list consist of two tuples where the first element is an atom, we rewrite the list as such:
{:ex_doc, "~> 0.19", [only: :dev, runtime: false]}
And because we can omit the square brackets when the keyword list is the final element of the tuple, we can further rewrite it like this:
{:ex_doc, "~> 0.19", only: :dev, runtime: false}
Note that it is still a three-tuple, and all the above representations are the same; only the visual representation changes. This trick is used in other places throughout Elixir; for instance defstruct is really a macro that takes one argument: a keyword list.
defmodule Order do
defstruct id: nil, item: nil, amount: 0
end
Other notable examples are the config/3 macro, and the use/2 macro which allows us to pass supervision options into a GenServer specification like this:
use GenServer, restart: :transient, shutdown: 5_000
Read more about the Elixir syntax in the Elixir Syntax Reference.
This week’s Code Elixir LDN challenge has now been posted:
# What will this return ?
MapSet.new(1..32) |> Enum.to_list()
# Observe what happens if we request 33 elements instead:
MapSet.new(1..33) |> Enum.to_list()
# Let's discuss what happens here;
# What is special about the number 33 and what does it mean ?
We’ll follow up tomorrow with an explanation.
MapSet.new(1..32) |> Enum.to_list()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
MapSet.new(1..33) |> Enum.to_list()
[11, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12]
MapSet.new(1..32)
#MapSet<[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]>
MapSet.new(1..33)
#MapSet<[11, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12]>
MapSet.new(1..34)
#MapSet<[11, 34, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12]>
I look forward to the explanation!
MapSet wraps maps, and maps change their internal representation from a linked list (basically it’s like a keyword list with <= 32 elements) to a, I think it was a hashed array, which will make the output look random. I.E. don’t rely on maps being ordered, because they aren’t, the reason they may come out ordered for small sizes is just an implementation detail. 
The explanation is now revealed
# What will this return ?
MapSet.new(1..32) |> Enum.to_list()
# Observe what happens if we request 33 elements instead:
MapSet.new(1..33) |> Enum.to_list()
# Let's discuss what happens here;
# What is special about the number 33 and what does it mean ?
A bunch of stuff is happening here. Elixir has a concept of protocols which provide polymorphism on data types and structures. In our example we pipe the result of generating a MapSet into the to_list/1 function on the Enum module. Enum is a module containing functions that work on data types implementing the Enumerable protocol; examples of these are lists, maps, and ranges. Enum can do all kinds of neat stuff on these, such as taking a slice of a range:
# Give me first 5 elements after the 10th element in the range 1 to 20
iex > Enum.slice(1..20, 10, 5)
[11, 12, 13, 14, 15]
Intuitively we would think a data structure has an order; for instance a Range is a sequence of numbers increasing (or decreasing) from the start point to the end point of the range. When we ask to turn a Range into a list using Enum.to_list/1 it will materialize into a list of numbers, going from first to last. A Range has a natural order, and so does a list—which is implemented as a linked list; the elements has an order based on the order they were inserted, as the element at the head of the list will point to the next in the list.
But this intuition fails when it comes to the Map data structure. If we ask for the list representation of a Map containing keys consisting of integers we might get fooled into believing that a Map has an reliable order:
iex > Enum.to_list(%{1 => :a, 2 => :b, 3 => :c})
[{1, :a}, {2, :b}, {3, :c}]
Which might seem odd when we try to construct a Map with 33 or more elements and observe what happens when we convert it to a list:
iex> Enum.into(1..33, %{}, fn (x) -> {x, x} end) |> Enum.to_list()
[{11, 11}, {26, 26}, {15, 15} | _output_omitted]
What is special about 33? Why did we get a seemingly random order in our return?
The technical explanation is that the Erlang Virtual Machine stores maps in different data structures depending on the number of elements in the Map . For a Map containing 32 or less elements it is stored in a sorted array—which explains why we observe an order iterating over the elements using the Enum and Stream functions—and when the Map contain more than 32 elements the Erlang VM will switch to a data structure called «hash array mapped trie,» which provides fast lookups for bigger data sets as well as very fast insertions. When we convert the big map to a list we will get whatever order the internal representation has; which is not intuitive.
For our initial example we convert a MapSet to a list. The MapSet data structure is useful for when we want to store terms in a set. It allows us to ask if a term is present, and perform comparisons between two sets, such as getting the difference or intersection, in a fast and efficient manner. Behind the scenes a MapSet uses a Map to store its values, so it inherit the performance from the Map , but also the unordered nature when the set grows above 32 elements.
To conclude:
A Map is an unordered data structure,
and we should never rely on the order of a Map
While we seemingly observe an order when we convert maps to lists, or iterate over them, we should never rely on the order of a Map. Assuming a reliable order could break our application in a future Erlang/OTP release, as the OTP team could choose to change the internal representation of maps. That said, it is fine to use the functions in the Enum module to iterate over a map, as long as no assumptions on the order of the elements are made.
https://en.wikipedia.org/wiki/Hash_array_mapped_trie
https://elixir-lang.org/getting-started/protocols.html
https://hexdocs.pm/elixir/Enumerable.html#content
https://hexdocs.pm/elixir/Map.html#content
https://hexdocs.pm/elixir/MapSet.html#content
Did you find this interesting?
This Elixir challenge is brought to you by the Code Elixir LDN team, if you would like to know more about the conference, speakers and training, visit the website.
Well technically a hash map has an order too, it’s just in hash order rather than element order. ^.^
© Copyright Elixir Forum | Terms | Privacy & Cookies
