LFE Friday - lists:delete/2
Today’s LFE Friday is about 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!") "Hello 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))
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)
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
(defmodule my-lists (export (delete 2))) (defun delete (item list) (delete item list ())) (defun delete ((item (cons head rest) checked) (when (=:= item head)) (lists:reverse checked rest)) ((item (cons head rest) checked) (delete item rest (cons head checked))) ((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.
(defmodule my-lists (export (delete 2))) (defun 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. Note that we have to explicitly test if the item is the head of the list using a guard which is done with
when. 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 checking2.
((item (cons head rest) checked) (when (=:= item head)) (++ (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.
((item (cons head rest) checked) (delete item rest (cons head checked)))
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.
((item () checked) (lists:reverse checked)))
We will also present an alternative implementation which directly returns the resulting list without keeping a reversed list of items checked so far.
(defmodule my-list (export (delete 2))) (defun delete ((item (cons head rest)) (when (=:= item head)) rest) ((item (cons head rest)) (cons head (delete item rest))) ((item ()) ()))
For a discussion on the relative merits of the two different ways of implementing
delete/2 see myth about tail-recursive functions.
Naive because this is not optimized for performance, or exhaustively tested for completely accurate behavior of
This can be more efficiently written as
(lists:reverse checked rest)as
lists:reverse/2is a function which reverses its first argument and appends its second argument. ↩