Pure Swift: A little deeper into generics (Xcode 6 Beta 5 and Beta 6)

At the end of the last blogpost I delivered myself a challenge to write a method that could remove duplicates from a String or an Array of any type. And here's progress so far. I'm half way and I'm not sure how much further I can continue without some serious brainwork.

This is what I have:

func identifyDuplicates<seq: SequenceType where seq.Generator.Element: Equatable>(s:seq, contains:(seq, seq.Generator.Element, Int) -> Bool) -> [Int] {
    
    var sequence = s
    var indArr = [Int]()
    var i = 0
    for a in sequence {
        if contains(sequence,a,i) {
        indArr.append(i)
        }
        i++
    }
    
 return indArr
}

This generic method can take an array or a string and can be called respectively:

let dupArr = identifyDuplicates([1,2,2,3,4,3,4,4], { (a:[Int], b:Int, c:Int) -> Bool in
    contains(prefix(a, c),b)})

var str = "Hello, playground"
let dupStr =  identifyDuplicates(str, {(a:String, b:Character, c:Int) in contains(prefix(a, c),b)})

It then returns an array of Ints identifying the index positions of the duplicates leaving the removal up to us.

Note the use made of a closure. The closure knows the types we a dealing with and allows us to do manipulations not necessarily possible within the generic context of the method itself.

Removing duplicates

To remove duplicates, given an array of Ints locating indices for a String, we could do this

var ind = 0
for i in dupString {
    str.removeAtIndex(i-ind)
    ind++
} 

assuming that we first write a String extension method like this:

extension String {
    
    mutating func removeAtIndex(ind:Int) {
        
        var str = prefix(self,ind)
        str += suffix(self,distance(self.startIndex,self.endIndex)-ind-1)
        self = str
    }
}

Practical reality

But really this is all overkill and unless further progress can be made we would be better off sticking to a String extension method:

extension String {
    
    mutating func removeAtIndex(ind:Int) {

        var str = prefix(self,ind)
        str += suffix(self,distance(self.startIndex,self.endIndex)-ind-1)
        self = str
    }
    
    func removeDuplicates() -> String {
        var arr = self
        var indArr = [Int]()
        var tempArr = self
        var i = 0
        for a in self {
            
            if contains(prefix(arr, i), a) {
                indArr.append(i)
            }
            
            i++
        }
        
        
        var ind = 0
        for i in indArr {
            arr.removeAtIndex(i-ind)
            ind++
        }
        return arr
    }
}

var str = "hello world"
    
str.removeAtIndex(4)

str.removeDuplicates()

and a separate method for Arrays, like the excellent one suggested by @ChromophoreApp:

@sketchyTech just fits :) func remDupes<T: Comparable>(a:[T]) -> [T] { return a.reduce([T]()) { ac, x in contains(ac, x) ? ac : ac + [x] } }
— Chromophore (@ChromophoreApp) August 11, 2014

Conclusion

While this isn't the aim I set out to achieve, and while time, or greater intelligence, might find a combined solution, I have learnt a bit about the way in which closures make for expanding what is possible with generics through allowing some more specific code.

At the same time, I have further work to do exploring more specific protocol adoption. So won't close the book on this or call it finished just yet.

Update - 19 August 2014 - Xcode 6 Beta  6

Xcode 6 Beta 6 heralds a new protocol - RangeReplaceableCollectionType - with a useful range of algorithms that pull Array and String closer together. We are now able to create the elusive generic method for removing duplicates from Strings or Arrays with one method. 

func deleteDuplicates<S:RangeReplaceableCollectionType where S.Generator.Element: Comparable>(seq:S, obj:S)-> S {
    let s = reduce(seq, obj){
        ac, x in contains(ac,x) ? ac : ac + [x]
    }
    return s
} 

It can be called in the following ways:

var str = "Hello, playground"
var arr = [1,2,3,4,5,6,6,5,4,3]

deleteDuplicates(str, String())
deleteDuplicates(arr, [Int]())

Once again thanks to @ChromophoreApp for his earlier input. And thanks also to Swift London for sharing the link that encouraged the input.

Update - 20 August 2014

I was so excited about RangeReplaceableCollectionType that I looked straight past the protocol from which it inherits (ExtensibleCollectionType) and, as @AirspeedSwift pointed out, this was stopping me from doing something even better (instantiating an S type instance within the function itself).

func deleteDuplicates<S:ExtensibleCollectionType where S.Generator.Element: Equatable>(seq:S)-> S {
    let s = reduce(seq, S()){
        ac, x in contains(ac,x) ? ac : ac + [x]
    }
    return s
} 

and this means we simply need to call the functions in this way:

var str = "Hello, playground"
var arr = [1,2,3,4,5,6,6,5,4,3]

deleteDuplicates(str)
deleteDuplicates(arr)

Note: It isn't the case that I couldn't do the same thing if the function continued to require a type that adopted the RangeReplaceableCollection protocol. But since I'm not performing any operations that require methods taken from that protocol there's no need to adopt it (and I didn't spot the init() method that had been inherited because I overlooked ExtensibleCollectionType in the first instance). I also don't need to specify Comparable when Equatable was all I needed for the Element type.

For even more generic functions that work with Array and String instances see this Gist.  

Follow @sketchytech