find() using Functional Programming

Question

I'd like to create a generic find() typically used in functional programming. In functional programming you don't work with array indices and for loops. You filter. The way it works is that if you have a list of say

["apple", "banana", "cherry"] 

and you want to find banana then you assign the array indices to the list elements by creating tuples

[(1, "apple"), (2, "banana"), (3, "cherry")] 

Now you can filter down to "banana" and return the index value.

I was trying to create a generic function for this but I get an error. What's wrong with this syntax?

func findInGenericIndexedList<T>(indexedList: [(index: Int, value: T)], element: (index: Int, value: T)) -> Int? {        
    let found = indexedList.filter {   // ERROR: Cannot invoke 'filter' with an argument list of type '((_) -> _)'

        element.value === $0.value
    }

    if let definiteFound = found.first {
        return definiteFound.index
    }
    return nil
}

UPDATE 1: I would like to use the above solution as opposed to using find() (will be deprecated) or in Swift 2.0 indexOf() because I'm trying to follow the Functional Programming paradigm, relying on general functions and not class methods.

Answer 1

The minimum change required to make this work would be to make T conform to Equatable and use the == operator.

func findInGenericIndexedList<T:Equatable>(indexedList: [(index: Int, value: T)], element: (index: Int, value: T)) -> Int? {
    let found = indexedList.filter {
        element.value == $0.value
    }

    if let definiteFound = found.first {
        return definiteFound.index
    }
    return nil
}

It doesn't really make sense to use === here because are usually going to be applying this to value types (especially if you are following functional paradigms) for which this is never true.

Beyond this I spent some time thinking about the problem and here is what I would do:

extension Array where Element : Equatable {
    func find(element:Array.Generator.Element) -> Int? {
        let indexedList = lazy(self.enumerate())
        let found = indexedList.filter {
            element == $1
        }

        let definiteFound = found.prefix(1)
        return definiteFound.generate().next()?.index
    }
}

Protocol extension on Array because it makes the syntax neater, lazy sequence to avoid checking every element, 0 indexed.

Answer 2

Here are a couple of thoughts.

I would still prefer to use the identity operator '===', because in my array I may have multiple items of the same value.

The identity operator === only works for reference types, like classes. It will never work for value types, like Strings or Ints, or structs, etc. You might take a look at the difference between value types and reference types, especially if you are interested in functional programming, which eschews reference types almost completely. When you are working with value types, there is only equality (==) - there is no identity. Two instances of the String "bananas" will never refer to the same identical object. They will always refer to two different Strings, though their values might be equal.

I want to delete the exact item that I passed to the function. Is it impossible to do this?

If you are working with value types, like Strings, then yes, it is impossible. There is no such thing as two different Strings that are the exact same item. Two Strings are always are always different objects, for the reasons stated above.

Note that if you work only with classes, and not value types, then you could use the === operator, but this would defeat much of what you are trying to do.

What this boils down to is that if you have an array of (index, value) tuples that looks like this:

[(0, "bananas"), (1, "apples"), (2, "oranges"), (3, "bananas")]

And you write a function that looks for tuples where the value is "bananas", you have a couple of choices. You can filter it and look for the first tuple in the array that has the value "bananas" and return the index of that tuple. In the above case it would return 0. Or, you could return all of the indexes in the form of an array, like this: [0, 3]. Or I suppose you could return some other arbitrary subset of the results, like the last index, or the first-and-last indexes, etc., but those all seem a little silly. The Swift standard library opts for returning the index of the first item that matches the search criteria for precisely this reason. None of the other options make a whole lot of sense.

But putting it back into the context of your question, none of the tuples that you find with the value of "bananas" are going to be the exact (identical) instance of "bananas" that you passed in to your search function. No two value types are ever identical. They may be equal, but they are never identical.

One more note - mainly for clarification of what you are even trying to do. In your first attempt at writing this function, you appear to already know the index of the item you are searching for. You pass it in to the function as a parameter, right here:

                                                                     // ----------vvvvv
func findInGenericIndexedList<T>(indexedList: [(index: Int, value: T)], element: (index: Int, value: T)) -> Int?

Just out of curiosity, is this a typo? Or do you actually know the index of the tuple that you are searching for? Because if you already know what it is, well... you don't need to search for it :)