Dicts with defaults, etc.

[StefanKarpinski]

This one is straight from Ruby: dicts with default values, provides either by a value (immutable) or a default value generator function. The Ruby style is (h,k)->... so that you can choose to cache the default value or not.

An interesting idea is having type-specific defaults for typed Dicts. Another interesting idea comes from @avibryant's talk at Hacker School: dicts naturally become a monoid if their values form a monoid.

Another generalization of Dict behavior would come from using different hashing functions. Not sure that's really a great idea though.

[johnmyleswhite]

Glad you remembered this one. I considered implementing it one day, then wasn't sure whether it should be a new type or just a breaking change in the existing Dicts.

[StefanKarpinski]

Yeah, I'm not sure. Kind of depends on if we can add this to Dicts without a performance penalty or not.

[StefanKarpinski]

So the main reason I've not done this yet is that I've been mulling over (somewhat sluggishly), what the interface should look like. As mentioned above, one way you could do this is like Ruby:

dict = Dict((d,k)->d[k]=0)

However, I was considering doing something like this instead:

plus_dict = Dict(+)
max_dict = Dict(max)
min_dict = Dict(min)

The idea here is that the operator not only provides defaults, but also acts as a combining operation for dict merges. So Dict(+) has +() = 0 as its default value, and if you merge two Dict(+) objects, their values are added. Likewise for Dict(max) the default value should be -Inf, although it seems that max() is not defined that way. I kind of like this idea, but fear it may be too cute.

[avibryant]

Makes sense to me; this is basically like the MapMonoid in algebird.

[StefanKarpinski]

Yup. Very much inspired by your talk at Hacker School.

[toivoh]

Sounds really interesting. I wouldn't be surprised if most uses of default dicts are motivated by an underlying monoid structure.

But what would the interface actually look like? If I have a d1 and d2 which are Dict(+), I would not be surprised if

d = merge(d1, d2)

would add the items together for keys present in both dicts. But how about

d[key] = value

Would that assign to d[key] (I hope so) or add to it?
And if it indeed assigns, how would I accumulate a value at a given key using the dict's monoid operator?

Also, why stop at monoids? It seems to me that a dict is pretty much a sparse vector.
One could define d1+d2 to do addition like with Dict(+), and d1*d2 to do multiplication like with Dict(*). On the other hand, that would use different default values for different operations, which seems kinda fishy. (Unless you really know that's what you want)

[johnmyleswhite]

I should chime in and note that:

Dict(+)
d = merge(d1, d2)

is a special case of the Series type in Python's pandas library.

[kmsquire]

Of note: https://github.com/JuliaLang/DataStructures.jl contains DefaultDict and DefaultOrderedDict implementations.

[kmsquire]

Addressed by #5519