How would you write a "pure" function that removes an element from a List?

Question

In Java (or any similar language) how would you write a Pure function (or method) that removes an element from a list.

If the element is in the list, we simply return a new (ideally immutable) list containing all the elements of the input list, minus the element we removed.

But how would you handle the case where the element isn't found in the list?

Let's assume the method receives 2 parameters, the list and the element to remove:

public SOMETHING remove(final List<String> list, final String element){
    // Copy the input list and remove the first occurrence of 'element', if I find it.
    // 
    // if I don't find it ... do something clever here ...
}

If I call this method, and element is not contained inside list:

• Throwing an exception would presumably make method "impure" (?)
• Modifying the input list and returning a boolean (similar to List#remove()) would presumable make the method "impure" (modifying the input would be a side-effect)
• Returning the input as output would seem unintuitive to me if I was calling this method.
• return an Optional.of(listCopy) (EDIT: added to my question after posting it)
• Any other ideas ?

EDIT

I should have mentioned that I only want to remove the first occurrence of element, so if the input list has multiple occurrences of element, I don't want to remove them all with a sigle call to my remove() method (e.g. using stream().filter()). I just edited the comment in my code example to reflect this. However, this is not fully relevant to my question, as my main question revolves around how to make the method intuitive to use AND remain "pure".

EDIT 2

I added an additional idea to the above suggestions. Returning Optional.of(listCopy) seems like the most elegant solution of the proposed solutions so far. It forces the caller to check if the requested operation was successful or not, AND (if it was successful), it returns a new list, thereby not modifying the original input list. If the operation was not successful (element wasn't found inside list), the method returns Optional.empty(). It seems to me this would also fulfil the below mentioned referential integrity.

Answer 1

Going through the points you mentioned:

1. Throwing an exception would presumably make method "impure" (?)
   • This is an implementation decision, if you want to return the same list or throw an exception. as for 'pure function' - as long as you're consistent and the same input yields the same result (or exception), you're good
2. Modifying the input list and returning a boolean (similar to List#remove()) would presumable make the method "impure" (modifying the input would be a side-effect)
   • this will make it non pure functional, as you'll have a side effect
3. Returning the input as output would seem unintuitive to me if I was calling this method.
   • don't see any problem with that actually. again, your call if it's a valid scenario or not. in terms of 'pure function', you're ok here

as for implementation, I think stream is the simplest, and returns new list so you're ok in terms of purity

return list.stream()
 .filter(e -> !e.equals(element))
 .collect(Collectors.toList());

Answer 2

How about:

public List<String> remove(final List<String> list, final String element) {
    List<String> result = new ArrayList<String>(list);
    result.remove(element);
    return result;
}

From the Wikipedia, it must:

• have the same return for the same inputs - can't see any reason why this wouldn't be true here, no randoms, no IO, etc
• be stateless - only parameters are dealt with in this function. May as well make it static

EDIT (just saw comment about returning a new list each time)

If you are trying to achieve functional-style code in Java, then the fact that it is a new list causes problems. You are probably referring to a property called referential transparency. To summarise, a value has referential transparency if it can be replaced with a reference to itself, and vice versa, without changing the semantics of a program. Java does not really support this, and this is one of the reasons Java is not truly functional.

In Haskell, (almost) all expressions have referential transparency, i.e. a list [1, 2, 3, 4] is not just equivalent to another list [1, 2, 3, 4], it is the same thing. This is similar to how in maths, 7 is the same thing as 7, it doesn't make sense to say "that 7 isn't the same 7 that I have in this equation".

Going back to Java, you require that subsequent calls return the same output. It is therefore up to you to define what you mean by "same". In the functional world, this is usually determined by values, (i.e. using Arrays.equals()). However, if you want to use == (i.e. 2 lists are equal if and only if they occupy the same location in memory), the functional style is probably not what you want.

Hope that clears it up.

Answer 3

Any mutation to the existing list fails "Property 1" per Wikipedia.

Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).

Your only real hope here is to return a new List with all of the elements copied over, except the one that you want to remove.

public List<String> remove(final List<String> list, final String element) {
    return list.stream()
                   .filter(e -> !Objects.equals(e, element))
                   .collect(Collectors.toList());
}

This also handles the "element not in list" scenario since you get back a new list instance with the same elements as the old one. Effectively, if the state of your data doesn't change, then there's no real harm in returning the same state.

Bear in mind, though - this is actually quite expensive and/or wasteful, and wouldn't really be a valuable exercise with collections.

Answer 4

You could build a new List and loop through the input array, adding every element that wasn't element, then return the new list

Answer 5

For example, using ListIterator:

ListIterator<Book> iter = books.listIterator();
while(iter.hasNext()){
    if(iter.next().getIsbn().equals(isbn)){
        iter.remove();
    }
}