The Maps Proposal

[José Valim]

Hello everyone!

The Erlang community has for long been hinting at having a native Maps/Dict/Hash implementation in the language and a proposal has been written from the OTP Team at Ericsson about it. I recommend everyone to take a look at it:

https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md

While there is still a lot of room open for discussion, this announcement is important because it settles down many things we have left open in Elixir. I will outline some broad strokes to see if everyone is agreement.

1) The current keywords syntax is not going anywhere. if(this, do: that) will still be a direct translation too: if(this, [{:do,that}])

A lot of Elixir and Erlang libraries will still expect a list of tuples and we are not going away from it. 

2) The Keyword module (not the syntax) will be fully replaced by Dict. Why?

The reason we have kept Keyword around is because we didn't know if the Maps proposal was going to support only atoms as keys (as the Keyword module) or any other data structure. If the Erlang team had decided for an Atom-only key approach, the Keyword module would be able to encompass our current solution and the new approach. However, since the Erlang team is settled on supporting any data type, it means the Keyword module becomes unnecessary.

That said, it is very likely usage of the Keyword module will soon have to be replaced by Dict. Today, all the functionality is there, so it is kind of a direct replacement.

3) I still haven't thought about which syntax Maps are going to have in Elixir. My main concern right now is that the language will have enough room to support maps as a first class citizen and I think we are well covered. :)

Keep in mind that there is no need to go ahead and change your codebases yet. I just want to clear that those changes may happen soon and I will keep everyone updated on the topic as we have more news from the OTP team.

Feedback is welcome!

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

[Alexei Sholik]

Tidbits:

* this EEP has merely been put online recently, it's not an announcement of its inclusion into Erlang just yet

* Maps in this proposal are aimed at replacing the previous proposal for Frames[1][2]. But some people would like to have both (at least the author of the original Frames proposal does :))

* Dict already supports what Keyword does and it will support Maps when they arrive to Elixir. That's what José means by saying that Keyword might go away soon.

[1]: https://groups.google.com/forum/?fromgroups#!topic/erlang-programming/X7rQ6HUmPPw
[2]: https://groups.google.com/forum/?fromgroups=#!topic/erlang-programming/4u8BDcH80z8

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Best regards
Alexei Sholik

[Dave Thomas]

That said, it is very likely usage of the Keyword module will soon have to be replaced by Dict. Today, all the functionality is there, so it is kind of a direct replacement.

I wonder a little about the cognitive dissonance that may be opening up here.

We talk about keyword lists, but may have no concept of keywords.

We talk about Dicts, but they're actually Maps. Or will HashDicts be Maps? Or...

And if we continue to use Dict as the API for k/v behavior, will it be a MapDict?

I am not saying this is necessarily bad. But this is all an interesting example of coupling, in the design sense. 

If we decide to keep the naming distance, then there will be a minor speedbump for people moving to Elixir from Erlang. They will be an even bigger issue for newcomers to both who have to reference Erlang libraries every now and then and remember to convert Dict into Map (and maybe :map into Dict).

So I'm wondering—if the intent is to mirror Erlang, shouldn't we bite the bullet and just go with Map, and maybe have a behavior for KVLookup, just in case there's a need for different abstractions?

Dave

 

[José Valim]

Ok, I should clarify a bit more.

Today, the Dict module is the behaviour. Anything that implements the Dict behaviour, well, behaves like a Dictionary. You can pass any data type to the Dict module and it will point to the proper implementation. We have two Dict implementations that ship by default with Elixir:

1) HashDict

2) List.Dict (maybe it should be called ListDict?)

HashDict is represented internally by a tuple and it hashes the keys for lookup, hence the name. List.Dict is simply a list of tuples where the first element is the key and the second is the value.

The existing Keyword module is nothing than a List.Dict with the limitation that keys can be only atoms. The Keyword and List.Dict modules are actually very similar and we had this duplication exactly because we were not sure where Erlang would take us. Now that we have a better perspective, we can start tidying up.

Maps will be a new implementation of the Dict behaviour. This means that, by using the Dict module, you will be able to manipulate HashDict, List.Dict and Map (or whatever module we put it in). You can also merge different types together and what not. You can also use any of HashDict, List.Dict or Map when looking for specific behaviour.

Does this make sense?

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

--

[Oren Ben-Kiki]

Obviously one can implement the Dict interface using anything, including some implementation of the Map proposal. However - there is non-trivial run-time overhead when working through the behavior interface. More importantly, there's no way you can use it in patterns.

I thought the idea in the Map proposal was to introduce new Erlang Map-specific syntax, which would be more efficient and also allow being used in patterns. If so, it would require adding some equivalent new Map-specific syntax in Elixir as well, which would not be dependent on the Dict interface.

[José Valim]

I thought the idea in the Map proposal was to introduce new Erlang Map-specific syntax, which would be more efficient and also allow being used in patterns. If so, it would require adding some equivalent new Map-specific syntax in Elixir as well, which would not be dependent on the Dict interface.

Yes, this is also going to happen. We can only know exactly how though after the Erlang proposal stabilizes.

[J David Eisenberg]

On Thursday, May 9, 2013 10:06:04 PM UTC-7, José Valim wrote:

I thought the idea in the Map proposal was to introduce new Erlang Map-specific syntax, which would be more efficient and also allow being used in patterns. If so, it would require adding some equivalent new Map-specific syntax in Elixir as well, which would not be dependent on the Dict interface.

Yes, this is also going to happen. We can only know exactly how though after the Erlang proposal stabilizes.

So, does this mean that the Keyword module is definitely going away, no matter what?

[José Valim]

So, does this mean that the Keyword module is definitely going away, no matter what?

It is very likely unless they drastically change the current Maps EEP.

I am sorry I can't confirm in advance but if it is going away, the source code replacement is supposed to be drop-in.

[Dave Thomas]

So, does this mean that the Keyword module is definitely going away, no matter what?

It is very likely unless they drastically change the current Maps EEP.

Does this mean that an interface such as

    People.sort_by asc: :name, desc: :state, asc: :age 

will no longer be supported (as Keyword allows duplicated keys, which is an improvement on Ruby IMO) and Map doesn't?

Dave

[Alexei Sholik]

Dave, good example!

The keyword list itself is not going away. That is, you will still be able to type "[a: 1, b: 2, a: 3]" and it'll be evaluated to "[{:a, 1}, {:b, 2}, {:a, 3}]".

Not sure if the Dict module will be able to work with those after Keyword is removed, but you will definitely be able to write your own function that handles the sorting the way you showed in your example.

--

You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[José Valim]

The following code:

    People.sort_by asc: :name, desc: :state, asc: :age 

Will still translate to:

    People.sort_by [{:asc,:name},{:desc,:state},{:asc,:age}]

So it will still work. The only difference is that to interact with it, we will use the Dict module instead of the Keyword module. In terms of source code, a s/Keyword/Dict replacement in the code base is all required to get up to date.

The only reason for Keyword to still exist was because there was a possibility for Erlang to introduce a new data type (that they were calling frames) that only accepted atoms as keys. But this possibility seems gone now.

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

--

[Alexei Sholik]

José, I was first! :)

[Dave Thomas]

So it will still work. The only difference is that to interact with it, we will use the Dict module instead of the Keyword module. In terms of source code, a s/Keyword/Dict replacement in the code base is all required to get up to date.

Will you be adding get_values/2 to Dict?

 

[Alexei Sholik]

> People.sort_by asc: :name, desc: :state, asc: :age

BTW, with new maps you will be able to write (syntax notwithstanding)

    People.sort_by "name": :asc, "state": :desc, "age": :asc

which is arguably a more intuitive approach for this task.

--

You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[José Valim]

Will you be adding get_values/2 to Dict?

I am so happy I brought this issue early on. :)

Per the wikipedia definition, a Dictionary does not have duplicated keys. That's why we have added them specifically to Keyword and I believe we shouldn't add them to Dict. I can see three options:

1) We would add those extra Keyword function to ListDict. However, since it also carries "Dict" in the name, it doesn't seem like a good fit

2) We could keep the Keyword module around and just remove the limitation that keys have to be atoms. Now, the question is: does it make sense to have a module called Keyword that accepts non-atom as keys?

3) The whole problem is that we will have two modules: Keyword and List.Dict with exactly the same functionality. So instead of trying to keep both around, should we come up with a new module that better represents what we want?

PS. To complicate matters, let's imagine we add maps to Elixir with the following syntax:

    %{ :foo => :bar }

Which is a map with :foo as key and :bar as value. Would we also want to support the following syntax?

    %{ foo: :bar }

and if so, would we also want the following to be available?

    [:foo => :bar] #=> [{ :foo, :bar }]

[José Valim]

BTW, with new maps you will be able to write (syntax notwithstanding)

    People.sort_by "name": :asc, "state": :desc, "age": :asc

which is arguably a more intuitive approach for this task.

I agree this example is better but Elixir itself has many use cases where we need duplicate keys, for example:

    defdelegate [sample: 0, sample: 1], to: AnotherModule

:)

[Oren Ben-Kiki]

How about renaming keyword to multimap, then? removing the restriction that the key must be an atom and adding get_values/2. It could be an implementation of multidict :-)

[Alexei Sholik]

My thoughts regarding extending support for duplicate keys to arbitrary dicts.

First of all, keyword lists are not collections. They are not meant to act as dictionaries, they are just a sugar for commonly used lists of tuples. An Orddict, for instance, is a collection, it has similar internal representation to keyword lists but it doesn't allow for duplicate keys.

Moreover, multimaps are not used that often. They're akin to multiple inheritance in this respect -- hardly any language has builtin support for them, although they could still come up theoretically. Even when you need a multimap, you can implement it by having a key pointing to a list of values. Erlang embraces this idea by providing functions append and append_list for most (all?) of its dicts. Even if you have a multimap in a language with a custom API, it is likely to be implemented as described: by putting values in lists to give an impression of recurring keys.

So, Keyword's support for duplicate keys can be handy, although I find it a bit inconsistent. For example,

iex(3)> Keyword.merge [a: 1, b: 2], [a: 3, d: 4, a: 4]
[a: 3, d: 4, a: 4, b: 2]

iex(4)> Keyword.merge [a: 1, b: 2, a: 2], [a: 3, d: 4, a: 4]
[a: 3, d: 4, a: 4, b: 2]

This simply doesn't strike me as the obvious behavior of merge function. Add to this the fact that Keyword.get/3 returns the value for the first key, Keyword.delete/2 removes all values for the given key and Keyword.put/3 removes all values for the given key before it adds the new one, it all starts to feel like a mess.

If we can come up with legitimate use-cases for the above functions that are common in Elixir code, we should probably keep Keyword but not advertise it as a Dict. It is already special and it's better keep it that way.

And no, I don't think Elixir needs builtin support for multimaps.

On Fri, May 10, 2013 at 8:45 PM, Oren Ben-Kiki <or...@ben-kiki.org> wrote:

How about renaming keyword to multimap, then? removing the restriction that the key must be an atom and adding get_values/2. It could be an implementation of multidict :-)

--

You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Dave Thomas]

If we can come up with legitimate use-cases for the above functions that are common in Elixir code, we should probably keep Keyword but not advertise it as a Dict. It is already special and it's better keep it that way.

And no, I don't think Elixir needs builtin support for multimaps.

+1 to both.

I would be happy to work on a refresh to Keyword if folks wanted.

Dave 

[Oren Ben-Kiki]

I certainly won't defend multimaps, they are pretty hairy (e.g., we pretty much abolished them from YAML). The only language I know of that uses them "regularly" is PHP - enough said :-)

But, as Jose pointed out, Elixir itself uses duplicate keys in many places. It seems reasonable there should be _some_ module to help out with handling them... and as long as such a module exists, you might as well be honest about what you call it.

--

[Alexei Sholik]

> It seems reasonable there should be _some_ module to help out with handling them... and as long as such a module exists, you might as well be honest about what you call it.

Yes, I'm in support for such a module too. But the current name "Keyword" does not imply any dict affiliation, so it's fine by me. We could rename it to OptionList or something similar. As long as it doesn't have "dict" or "map" in its name, we're OK with forgetting about the whole multimap discussion as if it never happened :)

[Oren Ben-Kiki]

OptionList reflects the intended common use case (and explains why it allows duplicates). It might look strange when used for another use case, but Keyword was also kind of a strange name, so we are probably not any worse off by calling it OptionList :-)

[Alexei Sholik]

If anyone here is interested in archaeology, here's the commit that changed Orddict to Keyword -- https://github.com/elixir-lang/elixir/commit/96f26c9299ba38e7139f2fc193c3553f4f8c0b22 (see also discussion in the referenced issue). I haven't found the actual proposal for the name on the issue tracker. We might have discussed it on IRC, but I can't remember.

There was also a brief moment when José was considering to make Keyword part of the Dict behavior family -- https://github.com/elixir-lang/elixir/issues/274. Apparently, it wasn't done back then and we all seem to agree now that nothing has changed in this respect: Keyword is meant to provide utility functions for keyword lists. Any coincidence with the functions from Dict behavior should be treated as just that -- a coincidence.

[José Valim]

So if we are really going to make a very explicit distinction in between Keyword and Dict, shouldn't we trim down the Keyword/OptionList module to remove the Dict like functions?

Because merging two Keyword/OptionsList together does not actually have very clear semantics. Should duplicate keys on both sides be kept? Or should we remove all entries on both lists and keep just one final key? In some cases, wouldn't option_list1 ++ options_list2 be enough?

Also, what would mean to add a new key? Do you want to remove all previous ones or do you want to add a new key and not care about the rest? If the latter, a simple [key: new_value|old] should be enough (as soon as we support this syntax anyway).

The trick part here is that the same representation could be either treated as Dict or as a Keyword list: it all depends on the function you are calling! Even further, the same function call can expect a Keyword with some keys being unique while others can be duplicated.

At least whenever you have duplicated keys in Keyword, you rarely end up doing an access like keyword["foo"] but you iterate the whole thing instead. For example, get_values could be easily written as a comprehension:

    lc { :key, value } inlist optionlist, do: value

Or if you prefer:

    Enum.map(optionlist, elem(&1, 1))

I guess what I am trying to say is: if you want to treat a key as unique, you can use the Dict module. If you want to treat a key as a set of values, you already have Enum and the basic operators ++ and |. I feel like proposing to use those existing tools is better than hiding everything under OptionList, which won't be able to hold both use cases anyway, leading to the inconsistencies that exist in the Keyword module today.

[Dave Thomas]

I think José is right, but I also don't think the problem is intractable. I think the answer might be to stop thinking of it as a list at all, and instead have an Opt module that was solely concerned with the kinds of things that functions to with options. So we'd have an API that allowed you to merge in defaults, to iterate keys, to iterate keys, but grouped  if there are duplicates, and so on. There'd be no need to ++ an OptionList, because everyone can pretend it isn't a list at all.

I'm a little tied up for a while, but if this approach is even mildly viable, I'd be happy to produce a draft api spec.

Dave

--

[Alexei Sholik]

Dave:

> I think the answer might be to stop thinking of it as a list at all, and instead have an Opt module that was solely concerned with the kinds of things that functions to with options.

This would be suboptimal. Knowing that keyword lists are lists of tuples actually makes them more flexible. You can use functions from Enum to iterate them seemlessly, you can use some functions from List too. Finally, you can pass them to Erlang and back and use the facilities of Erlang's :proplists module.

When I suggested that we came up with legitimate use-cases for Keyword (or its successor) I meant defining a set of functions that make common sense. For instance, Keyword.merge should not make the cut in my opinion because it's not clearly defined how it works when both lists have the same repeating keys with different values. In the same vein, things like put, get, delete just don't have one true interpretation: sometimes you want to peek at the last occurrence of a key, other times you want the first one.

Those are the reasons which José must have had in mind when suggesting to drop Keyword. In fact, I just realized that List.Dict actually works with lists of tuples, not orddicts. Moreover, List.Dict actually supports repeating keys:

iex(1)> List.Dict.delete [a: 1, b: 2, a: 3], :a
[b: 2]

iex(3)> List.Dict.put [a: 1, b: 2, a: 3], :a, 10 
[a: 10, b: 2]

Now this, I think, is broken. While it's convenient to create "dicts" with the short keyword syntax, I would much rather prefer List.Dict support only orddicts.

This is getting long and it doesn't look we're coming to a conclusion any time soon here. Dave, I think you should go ahead with your API proposal. You could implement it as a library so we all would have a more tangible argument added to this discussion.

To sum up, I agree with José that it doesn't make sense to keep both Keyword and List.Dict as long as List.Dict supports recurring keys too (the rationality of which I would like to discuss in a separate thread). But if we have keyword lists and they are quite commonly used, there will definitely be a set of functions that many of us will find ourselves reimplementing for keyword lists.

Those could be good candidates for a dedicated module that would provide utility functions for keyword lists. But at the same time one could argue that we're trying to reinvent the wheel here, because Erlang already has :proplists that provide a different set of functions from that of :orddict.

I can't see this discussion coming to an end any time soon.

[José Valim]

This would be suboptimal. Knowing that keyword lists are lists of tuples actually makes them more flexible. You can use functions from Enum to iterate them seemlessly, you can use some functions from List too.

I agree with this. Keyword arguments are syntax sugar for a list of tuples. We could have an Opt module but I'd like to evaluate how far we can go without it.

 

List.Dict actually supports repeating keys:

Whatever implementation we come up of ListDict, it will "support" repeating keys. Or it will delete just the first one or it will delete all, which can both be valid behaviours for something with duplicate keys. The reason for that is because it is only a list and people can manipulate them in whatever way they please. :)

 

Now this, I think, is broken. While it's convenient to create "dicts" with the short keyword syntax, I would much rather prefer List.Dict support only orddicts.

It was an orddict and we reverted it because it was a pointless limitation. In fact, the current implementation using lists:keyfind (and therefore non ordered) is faster than the order dependent one for dicts with a small number of elements (n <= 20). I am not worried about n > 20 though because both will be extremely slow compared to better solutions like HashDict. More limited and slower doesn't look like a fair trade-off to me. :)

[Joe Armstrong]

There's a very important property of Erlang maps that is not immediately obvious - I'll mention it here

so that it doesn't get missed.

   In the erlang maps (that will be) there are two value update operators

       Key := Val     and  Key => Value

They behave differently - in Erlang

 

        OldMap # { Key := Val }

Fails if Key is not in the old map    Key => Val always succeeds and adds a new key to the oldmap

There are two very good reasons for this

    1) updates with only := allow the old and new maps to share all the key descriptors

       

so if we have a list of one million maps all with the same keys they will only be one key

descriptor not one million.

    (this will give significant space savings for saving XML trees, database records etc and

      allows loads of smart optimizations in the VM)

   2) it traps inadvertent spelling mistakes. if you in a few thousands of code say

       

         Old # { persan := "fred"} it's probably a typo - you meant to say person := "fred"

    you don't want to create a bad item in the map and have it there forever and crash your program

    way downstream of where the error occurred. You should fail immediately.

    I have no idea about how you will represent erlang maps in elixir - but this essential point should not

be missed - because it is essental to the space and time optimisations that can be performed later

Cheers

/Joe

[Dmitry Aleksandrov]

Which syntax are you planning to use for maps in Elixir?

What time, are you planning the maps syntax? (After the release of R17)

On Friday, 10 May 2013 01:54:26 UTC+2, José Valim wrote:

Hello everyone!

The Erlang community has for long been hinting at having a native Maps/Dict/Hash implementation in the language and a proposal has been written from the OTP Team at Ericsson about it. I recommend everyone to take a look at it:

https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md

While there is still a lot of room open for discussion, this announcement is important because it settles down many things we have left open in Elixir. I will outline some broad strokes to see if everyone is agreement.

1) The current keywords syntax is not going anywhere. if(this, do: that) will still be a direct translation too: if(this, [{:do,that}])

A lot of Elixir and Erlang libraries will still expect a list of tuples and we are not going away from it. 

2) The Keyword module (not the syntax) will be fully replaced by Dict. Why?

The reason we have kept Keyword around is because we didn't know if the Maps proposal was going to support only atoms as keys (as the Keyword module) or any other data structure. If the Erlang team had decided for an Atom-only key approach, the Keyword module would be able to encompass our current solution and the new approach. However, since the Erlang team is settled on supporting any data type, it means the Keyword module becomes unnecessary.

That said, it is very likely usage of the Keyword module will soon have to be replaced by Dict. Today, all the functionality is there, so it is kind of a direct replacement.

3) I still haven't thought about which syntax Maps are going to have in Elixir. My main concern right now is that the language will have enough room to support maps as a first class citizen and I think we are well covered. :)

Keep in mind that there is no need to go ahead and change your codebases yet. I just want to clear that those changes may happen soon and I will keep everyone updated on the topic as we have more news from the OTP team.

Feedback is welcome!

[Dmitry Aleksandrov]

What time, are you planning to add the maps syntax? After release of R17 or before?