Dictionaries

[byorgey]

It should be possible to program with dictionaries/maps in Swarm. Some options include:

1. Now that we have recursive types, it's totally possible to just program dictionaries as a library, as is done in e.g. Haskell. For example we could define a recursive type of binary trees and implement maps as balanced binary trees storing key/value pairs allowing for $O(\log n)$-time operations. See Dictionary example #2161 .
2. That works well in Haskell since GHC is an amazingly good optimizing compiler; in Swarm-lang it would result in a rather slow dictionary library. Taking a cue from e.g. Python, we could also have dictionaries built in as a language primitive, so under the hood they could use actual Haskell Maps.
3. One could also imagine trying to co-opt the record system to build dictionaries, but (1) records can't be polymorphic in the key type, (2) the type of a record must strictly list all its fields, and (3) records have heterogeneous value types, whereas dictionaries are homogeneous in the value type.

[xsebek]

I started working on 1. in #2161. Records + Recursive types look promising, I wonder how performant they will be.