[erlang-questions] Help on dictionary search

[Richard A. O'Keefe]

"Bob Cowdery" <Bob.Cowdery@REDACTED> wrote:
	I have a dictionary of the form 
	[ {class, [Pid, Pid, Pid ...]},
	  {class, [...]},
	  ...].
	A given Pid can appear in one or more classes.  Given a Pid I
	want to delete all instances of that Pid from the dictionary and
	if the class then has an empty list to remove the class.
	Generally I look up the dictionary by class and don't mind a
	linear search for the delete as its occational.

The best way to do this is to use the library, but you knew that.
lists:delete(Elem, List) is clearly appropriate for deleting something
from a list.  If we didn't already have it,

    delete(X, [X|T]) -> T;
    delete(X, [H|T]) -> [H|delete(X, T)];
    delete(_, []   ) -> [].

Or using list comprehension syntax,

    delete(X, L) -> [Y | Y <- L, Y /= X].

So you are going to have to do something to every {Class,Pid_List} tuple
in your dictionary.  It's a simple recursion, complicated only by the
need to decide whether to put something back or not:

    two_level_delete(Elem, [{Class,List}|Tuples]) ->
	case lists:delete(Elem, List)
	 of  []    -> two_level_delete(Elem, Tuples)
	  ;  List1 -> [{Class,List1} | two_level_delete(Elem, Tuples)]
	end.

It's really not surprising that a structure with two levels of lists
has an algorithm with two levels of loops.

List comprehensions can be helpful.  In particular, they let us combine
"map" (do something do each element) with "filter" (select some elements).
Erlang list comprehension syntax, according to section 6.22 of the
reference manual, is rather limited compared with other functional languages
that have list comprehension, where you can bind a new variable in the
qualifiers.  What I want to write is

    two_level_delete(Elem, Dict) ->
	[{Class,List1} ||
	    {Class,List0} <- Dict,
	    List1 = lists:delete(Elem, List0),
	    List1 .= []].
	    
You _can_ write this, but it doesn't work, because Erlang takes
(<variable> = <expression>) in a qualifier list as just an expression
whose result should be true or false, and of course it's a list.  This is
a real PAIN.  One hack would be to write
	List1 <- [lists:delete(Elem, List0)],
which is ugly.  In this case, we can fold the binding into the test, which
is even uglier.

    two_level_delete(Elem, Dict) ->
	[{Class,List1} ||
	    {Class,List0} <- Dict,
	    (List1 = [X || X <- List0, X /= Elem]) /= []].

All things considered, the simple hand-written recursion calling
lists:delete/2 is probably the easiest read in this case.