Core: Should Dict.keys return a Set?

[rtfeldman]

Dict.keys has this signature:

keys : Dict comparable v -> List comparable

It seems like Set would make more sense for the return type than List, as the keys in a Dict are:

1. unique
2. not ordered

...whereas the elements in a List are ordered and not necessarily unique.

[evancz]

It's this way based on what I was used to in Haskell, so not the best reasoning.

Best argument I can come up with is that typically I want the keys as a list if I am asking for them. Probably should look at uses of this function in the wild and see how many would be better if it was a set.

Did this come up for you in a particular scenario?

[rtfeldman]

Yeah, I have a couple of Dicts that map database IDs to records with info used in rendering. The server just wants the ids, not the records, so I use Dict.keys to get them during serialization.

Since I have to give the server a list of _unique_ ids, I end up calling Dict.keys, then later Set.fromList to guarantee uniqueness, then later List.fromSet so I can pass the ids to Json.Encode.

It's barely an inconvenience, but it surprised me because I'm used to Java, which only offers the Set option - and which seems more semantically appropriate.

[TheSeamau5]

Maybe there should be a choice. The default Dict.keys would return a Set emphasizing the uniqueness nature of the keys whereas Dict.keysAsList would return a list of keys without having to call Set.toList.

[jvoigtlaender]

Well, Dict.keysAsList (or actually the current Dict.keys) is just Dict.toList >> List.map fst.

I'm with Richard here, that the Dict.keys function would more semantically meaningfully return a set.

And if one wants a list, that functionality is already there (with Dict.toList).

[evancz]

So I think this idea makes sense, but I'd want to do a comprehensive overhaul of core APIs all at once. We are starting to see some ideas of how we can break things up or make the core data structures work together better, so I'd like to aggregate all those ideas and sort out how to combine them.

I have been talking to a bunch of folks who maintain open source projects and learned some tricks about closing issues more efficiently, even when it's a good idea that we should revisit at a later time. So I want to start closing issues like this and moving the most promising ones to #322 so we can do a comprehensive review when it's time.

[rtfeldman]

Love it! :+1:

[mgold]

So I know I'm late to this party, but I was thinking: since Dicts and Sets have the same representation except that a set never looks at the values, would it work to just hand the same dict object over and say it's a set? That way this function could run in O(1) rather than O(n) time. I don't think this is possible to implement because Dicts are actual Elm, not a native library, but in theory...

[rtfeldman]

Bonus! :D

On Sun, Nov 8, 2015, 9:29 PM Max Goldstein [email protected] wrote:

So I know I'm late to this party, but I was thinking: since Dicts and Sets
have the same representation except that a set never looks at the values,
would it work to just hand the same dict object over and say it's a set?
That way this function could run in O(1) rather than O(n) time. I don't
think this is possible to implement because Dicts are actual Elm, not a
native library, but in theory...

—
Reply to this email directly or view it on GitHub
https://github.com/elm-lang/core/issues/317#issuecomment-154867945.