Erlang Thurday – lists:delete/2

Today’s Erlang Thursday in lists:delete/2.

lists:delete/2 takes a Erlang term as it’s first argument, and will remove that item from the list passed in as the second argument.

lists:delete(1, [8, 7, 6, 5, 4, 3, 2, 1]).
% [8,7,6,5,4,3,2]
lists:delete(4, [1, 1, 2, 3, 5, 8]).
% [1,1,2,3,5,8]
lists:delete(72, "Hello World!").
% "ello World!"
lists:delete(d, [a, b, c, d]).
% [a,b,c]
lists:delete(4, []).
% []
lists:delete({b, 2}, [{a, 1}, {b, 2}, {c, 3}]).
% [{a,1},{c,3}]
lists:delete([1, 2, 3], [[4, 5, 6], [7, 8, 9], [1, 2, 3]]).
% [[4,5,6],[7,8,9]]

Note that lists:delete/2 only removes the first item found in the list, and leaves any other occurrences of the item in the list.

€lists:delete(1, [1, 1, 2, 3, 5, 8]).
% [1,2,3,5,8]

As lists:delete/2 was a easy function to demonstrate, and leaving it at this would be a very short post, I thought it might be worth showing a how you might write a very naive1 implementation of lists:delete/2 yourself.

-module(my_lists).

-export([delete/2]).

delete(Item, List) ->
    delete(Item, [], List).

delete(Item, Checked, [Item|Rest]) ->
    lists:reverse(Checked) ++ Rest;
delete(Item, Checked, [Head|Rest]) ->
    delete(Item, [Head | Checked], Rest);
delete(_Item, Checked, []) ->
    lists:reverse(Checked).

Let’s start with our delete function as we expect it to be called from the outside world.

my_lists:delete/2 is the nice API function that just calls delete/3 which is a “private” function (not exported) so the consumer doesn’t have to worry about passing in the accumulator for the items we have checked so far, which we pass as an empty list for the initial value.

-module(my_lists).

-export([delete/2]).

delete(Item, List) ->
    delete(Item, [], List).

The first function clause of delete/3 uses pattern matching to check if the item we want to delete is also the first item in the rest of the list to check. If the pattern match succeeds, we have found the first occurrence of the item to remove! We can stop processing the list and return the result, which is the reverse of the list of items we have checked so far combined with the rest of the items we never got around to checking.

delete(Item, Checked, [Item|Rest]) ->
    lists:reverse(Checked) ++ Rest;

The second clause “knows” that the item we are wanting to delete and the first item in the rest of the list don’t match. How does it “know”? Because if they did match, the first clause would have matched and this clause would not have been evaluated. As we haven’t found the item to remove, we add the item held by Head to the list of Checked items, and then continue calling delete/3. The fact that we are passing a new list of the checked items by prepending Head to the list in Checked is why we need to reverse Checked in the first and third function clauses.

delete(Item, Checked, [Head|Rest]) ->
    delete(Item, [Head | Checked], Rest);

The third, and final, clause of delete/3 has reached the end of the list and not found the item, so we just return the list we have reversed it.

delete(_Item, Checked, []) ->
    lists:reverse(Checked).

There you have it, a very naive1 implementation of your very own version of lists:delete/2.

–Proctor

1. Naive because this is not optimized for performance, or exhaustively tested for completely accurate behavior of lists:delete/2. back

Leave a Reply

Your email address will not be published. Required fields are marked *