Immutable dictionaries in Haskell
update key1 value obj = \key2 -&gt; if key2 == key1 then value else obj key2
access = id


Given the above definitions, your examples should work. Also, you can define an empty dictionary as const x where x is the default value for keys not in the dictionary.