Why does MapSet use empty lists instead of `nil` for the values of the maps keys?

I was playing around with MapSet, and I turned it into a plain map with Map.from_struct(). I was aware that underneath it was essentially just using map keys to ensure that it was a set, but I wasn’t sure why instead of all the values being nil, they are all empty lists ([]). Is there a reason why?

iex(16)> MapSet.new() |> MapSet.put(:a) |> MapSet.put(:b) |> Map.from_struct
%{map: %{a: [], b: []}, version: 2}

I don’t know why they have choosen the empty list, though it might be because it’s a highly optimised value in the beam itself.

But it’s not nil because it’s behaviour for access behaviour.

Looks like it was done to reduce space used when serialised using Erlang term format


Thanks for finding that. Very interesting that an empty list is so much smaller than nil when converted to binary (in fact it was smaller than anything else I could find).

The empty list is basically the NULL pointer internally. That’s why it is that small. It can be represented in a single byte which is usually used to tag the type of the following data.

1 Like

In BEAM there is no nil (not true and false), these are just regular atoms nil == :nil. That is why the empty list, which is “special value” has the smallest representation (in ETF nil need to encode its name as well as it can not exist on target machine or can be in different place, while the empty list will always be there and will always occupy the same “space” in all instances).

1 Like

Well technically in the BEAM the empty list of [] is called the nil type internally, that’s traditional among many languages, the empty list is nil, I don’t know why Elixir uses an atom for that, it’s still really really weird to me even to this day… I still assert that nil in Elixir should have originally mapped to [] on the BEAM as one would expect a nil type to do. ^.^;

1 Like