Map

Map

Map value is persistent collection key-value pairs such that each key value exists at most once in the collection. Value parts of pairs can be of any type, but keys must be some of following type:

• int
• string
• float
• list (of items being one of these types)
• boolean

Different types of values can exist in keys of same map (as well as in values).

Example:

./funla -eval "map(1 'one' '1' 1 0.5 'half' list(1 2) func() 'ok' end)"
map(0.5 : 'half', '1' : 1, list(1, 2) : func-value: file:  line: 1 pos: 66, 1 : 'one')

Maps are persistent meaning that map values cannot be modified. Adding to map or deleting from map produce new map value leaving original map as it is, so maps are effectively immutable. Performance penalty (copying data) is avoided by using structural sharing so that parts of data is shared between versions of maps.

Implementation of map is based on persistent red-black tree presented by Chris Okasaki in his book Purely Functional Data Structures. Okasaki, Chris (1998). Purely functional data structures (1 ed.). Cambridge, U.K.: Cambridge University Press. ISBN 9780521631242

Deletion of key-value pair remains complicated in Okasaki's solution and that is solved in FunL by using "tombstone" method so that by default key-value is not removed but marked as being deleted (this is done by path copying as in insertion as original map can not be modified). When number of deletions exceed certain limit new map is created so that items which are marked as deleted are not included.

Operators for map

Following operators are useful for map:

• map : creates new map
• put : add key-value pair
• get : get value for given key
• getl : get value for given key (and information whether key was found)
• del : remove key-value pair (by key)
• dell : remove key-value pair (by key) and information about key found in map
• in : inquiry for key being in map
• vals : list of all values in map
• keys : list of all keys in map
• keyvals : list of all key-value pairs in list (pair as list of two items)
• len : number of key-value pairs in map
• empty : has map any key-value pairs