Erlang Central

Difference between revisions of "Hash with Immutable Keys or Values"

From ErlangCentral Wiki

 
(answer the problem a bit differently, push existing answer down to Discussion)
Line 4:Line 4:
  
 
== Solution ==
 
== Solution ==
 +
 +
The provided hash-table-like modules don't offer immutability.  If you really want this, however, you can always use your own interface to the data structure, which checks to make sure that you don't change anything you don't want changed.  This interface might also ensure that only certain types of data are written, or log elsewhere what data is written, and so on.
 +
 +
Here is a silly example of an 'immutable hash' library, in the form of a process that prevents double-puts into its process dictionary.  A real implementation would depend on real needs.
 +
 +
<code>
 +
-module(immutable_hash).
 +
-export([new/0, loop/0, set/3, lookup/2]).
 +
 +
new() -> spawn(?MODULE, loop, []).
 +
 +
loop() ->
 +
    receive
 +
        M={Pid,set,K,V} ->
 +
            case get(K) of
 +
                undefined -> put(K,V),
 +
                            Pid ! {self(),ok,M},
 +
                            loop();
 +
                _ -> Pid ! {self(),already_defined,M},
 +
                          loop()
 +
            end;
 +
        M={Pid,lookup,K} -> Pid ! {self(),get(K),M},
 +
                            loop()
 +
    end.
 +
 +
lookup(Hash,K) ->
 +
    Hash ! M={self(),lookup,K},
 +
    receive {Hash,Res,M} -> Res end.
 +
 +
set(Hash,K,V) ->
 +
    Hash ! M={self(),set,K,V},
 +
    receive
 +
        {Hash,ok,M} -> ok;
 +
        {Hash,already_defined,M} -> {error,already_defined}
 +
    end.
 +
</code>
 +
 +
<code>
 +
1> H = immutable_hash:new(),
 +
<0.574.0>
 +
2> immutable_hash:set(H,test,5).
 +
ok
 +
2> immutable_hash:set(H,test,6).
 +
{error,already_defined}
 +
3> immutable_hash:lookup(H,test).
 +
5
 +
</code>
 +
 +
== Discussion ==
  
 
In some ways, Erlang dict Dictionaries are immutable by design. Each time you insert a value into a dictionary, it creates a brand new dictionary containing the data from the old dictionary, plus the newly inserted entry.
 
In some ways, Erlang dict Dictionaries are immutable by design. Each time you insert a value into a dictionary, it creates a brand new dictionary containing the data from the old dictionary, plus the newly inserted entry.
Line 10:Line 59:
  
 
ets tables are more problematic, because the permit updates to the table by name, and Erlang's single-assigment behavior does not provide any protection here.
 
ets tables are more problematic, because the permit updates to the table by name, and Erlang's single-assigment behavior does not provide any protection here.
 
== Discussion ==
 
  
 
This seems to be an area where Erlang can only provide this functionality if the programmer uses the single-assignment nature of the language to proper use.
 
This seems to be an area where Erlang can only provide this functionality if the programmer uses the single-assignment nature of the language to proper use.
  
 
[[Category:CookBook]][[Category:HashRecipes]]
 
[[Category:CookBook]][[Category:HashRecipes]]

Revision as of 17:09, 24 September 2006

Problem

You would like to have a hash table whose values or keys couldn't be modified once set.

Solution

The provided hash-table-like modules don't offer immutability. If you really want this, however, you can always use your own interface to the data structure, which checks to make sure that you don't change anything you don't want changed. This interface might also ensure that only certain types of data are written, or log elsewhere what data is written, and so on.

Here is a silly example of an 'immutable hash' library, in the form of a process that prevents double-puts into its process dictionary. A real implementation would depend on real needs.

-module(immutable_hash).
-export([new/0, loop/0, set/3, lookup/2]).

new() -> spawn(?MODULE, loop, []).

loop() ->
    receive
        M={Pid,set,K,V} ->
            case get(K) of
                undefined -> put(K,V),
                             Pid ! {self(),ok,M},
                             loop();
                _ -> Pid ! {self(),already_defined,M},
                           loop()
            end;
        M={Pid,lookup,K} -> Pid ! {self(),get(K),M},
                            loop()
    end.

lookup(Hash,K) ->
    Hash ! M={self(),lookup,K},
    receive {Hash,Res,M} -> Res end.

set(Hash,K,V) ->
    Hash ! M={self(),set,K,V},
    receive
        {Hash,ok,M} -> ok;
        {Hash,already_defined,M} -> {error,already_defined}
    end.
1> H = immutable_hash:new(),
<0.574.0>
2> immutable_hash:set(H,test,5).
ok
2> immutable_hash:set(H,test,6).
{error,already_defined}
3> immutable_hash:lookup(H,test).
5

Discussion

In some ways, Erlang dict Dictionaries are immutable by design. Each time you insert a value into a dictionary, it creates a brand new dictionary containing the data from the old dictionary, plus the newly inserted entry.

If you wish to have a read-only dictionary, you can structure your program so that the dict term is passed into functions for use, but that you never receive a new dictionary value from another function. In this way, the single-assignment nature of Erlang guarantees that the dictionary is unchanged.

ets tables are more problematic, because the permit updates to the table by name, and Erlang's single-assigment behavior does not provide any protection here.

This seems to be an area where Erlang can only provide this functionality if the programmer uses the single-assignment nature of the language to proper use.