Erlang code critique

Question

Hi,

I am trying to get my head round some basic erlang functionality and I could do with some comments on the following.

I have the following erlang code that takes a list of tuples and returns a list minus an element if a key is found:

delete(Key, Database) ->
    remove(Database, Key, []).

remove([], Key, Acc) ->
    Acc;
remove([H|T], Key, Acc) ->
    if
        element(1, H) /= Key ->             
            [H| remove(T, Key, Acc)];
        true  -> 
            remove(T, Key, Acc)
    end.

Is this a good way of doing this?

The if statement seems incorrect.

Also is my use of the accumulator Acc making this tail recursive?

Cheers

Paul

Answer 1

No, your usage of Acc doesn't make it tail recursive. Your branch of if returns [H| remove(T, Key, Acc)] which is not tail call and this branch would be used most of time. To be more precise your usage of Acc is useless because it would be [] whole time, you don't change its value at all. Correct code should look like.

delete(Key, Database) ->
    remove(Database, Key, []).

remove([], Key, Acc) ->
    lists:reverse(Acc);
remove([H|T], Key, Acc) ->
    if
        element(1, H) /= Key ->             
            remove(T, Key, [H|Acc]);
        true  -> 
            remove(T, Key, Acc)
    end.

But if your list members are always pairs I would prefer direct pattern match:

delete(Key, Database) ->
    remove(Database, Key, []).

remove([], Key, Acc) ->
    lists:reverse(Acc);
remove([{Key, _}|T], Key, Acc) ->
    remove(T, Key, Acc);
% if it should delete only first occurrence then lists:reverse(Acc, T);
remove([H|T], Key, Acc) ->
    remove(T, Key, [H|Acc]).

But I think this is example where can apply Myth: Tail-recursive functions are MUCH faster than recursive functions so I would use much simpler recursive version:

delete(Key, []) -> [];
delete(Key, [{Key, _}|T]) -> delete(Key, T);
% if it should delete only first occurrence then just T;
delete(Key, [H|T]) -> [H | delete(Key, T)].

Answer 2

As mentioned, there is a standard module function that already does this (proplists:delete). Shouldn't need to say more, but...

I'd tend to keep the original method name (delete), but have a local version including the accumulator as parameter. The context makes me think the order of the tuples in the "database" doesn't matter, so that a lists:reverse isn't necessary.

-module(foo).
-export([delete/2]).

delete(Key, Database) ->
    delete(Key, Database, []).

delete(_Key, [], Acc) ->
    Acc;
delete(Key, [{Key, _} | T], Acc) ->
    delete(Key, T, Acc);
delete(Key, [Entry={_, _} | T], Acc) ->
    delete(Key, T, [Entry | Acc]).

A couple things here:

• tail-recursive; in general I think it is safer to stick with tail-recursion -- while there are optimizations for body recursive calls, you'd really need to do some performance measurement with realistic (for your application) data to make a comparison
• note that we're not accepting any old list here; the Entry pattern match in delete/3 helps ensure this (depending on what this is for, you may or may not want this)