[swift-evolution] Dropping Comparable requirement for indices

[Dave Abrahams]

on Thu Jul 07 2016, Haravikk <swift-evolution at swift.org> wrote:

>> On 7 Jul 2016, at 02:41, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> 
>> on Wed Jul 06 2016, Haravikk <swift-evolution at swift.org> wrote:
>> 
>
>>>> On 6 Jul 2016, at 03:39, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>> For example, with
>>>> Comparable indices, you can't build a linked list that supports
>>>> restructuring (e.g. insert, delete, splice) in O(1) without invalidating
>>>> indices... not even an unsafe linked list with reference semantics.
>>> 
>>> I think the question is why you need to retain indices in these cases?
>>> 
>>> When it comes to these operations I wonder if we might want to
>>> investigate something like a mutating iterator; you might still use an
>>> index to jump to an initial position, but then use .insert(),
>>> .remove() etc. methods of the iterator to perform modification without
>>> the need to track indices at all. 
>> 
>> There is no way, AFAIK, to implement important algorithms like rotate
>> binarySearch and several others, without having some representation of
>> position within a collection.
>> 
>>> This is essentially how you want to edit trees anyway, as indexing
>>> them isn't especially pretty, as it avoids the need to track the
>>> indices at all for these operations, and many common cases should work
>>> well when done as part of an iterator in this way.
>> 
>> I don't know what you mean by “track,” here.  We don't track the
>> indices of an array.
>
> By track I just mean store in a variable.
>
> As an example, consider removing multiple values using a closure:
>
> 	let delete:(Int) -> Bool = { ($0 % 2) == 1 } // Delete all odd numbers
> 	let filtered = myArray.filter { !delete($0) } // Produces new copy of array with elements filtered
>
> 	// In-place removal
> 	var index = myArray.startIndex, indices:[Array<Int>.Index] = []
> 	for eachElement in myArray {
> 		if delete(eachElement) { indices.append(index) }
> 		myArray.formIndex(after: &index)
> 	}
> 	for eachIndex in indices { myArray.remove(at: eachIndex }

I'm afraid that doesn't work (remove elements from [0, 1] with the
predicate {true}), and even if it did work it would take O(N^2) time and
O(N) space.  The right algorithm is O(N) time and O(1) space.

> The latter case only works with types where you know that there's a
> safe way to use the indices (removing in reverse order doesn't
> invalidate earlier indices of Array) so it's not suitable for generic
> collections. 

Exercise for the reader: write a generic one that works for any
RangeReplaceableCollection.  It should be easy.  Hint: you only want one
call removeSubrange.

> Since it requires iterating myArray anyway, then if the removals could
> be performed at the same time it would eliminate the need to store and
> then use indices at all, and would be a much better way to work with
> linked-lists, trees and so-on. So with a mutable iterator for example
> the in-place removal would look like:
>
> 	var iterator = myArray.makeMutatingIterator()
> 	while let eachElement = iterator.next() {
> 		if delete(eachElement) { iterator.remove() }
> 	}

In general, because arrays have value semantics, there's no way to
mutate the array through another object such as a mutating iterator.
And even if there was a way, it would still force the whole
array's storage to be cloned at least once, which is not something we
want to pay for.

> Maybe this isn't directly applicable to this topic, but this for
> example seems like a better solution to the linked list problems
> raised than removing Comparable as a requirement which was my intended
> point, that perhaps this isn't necessary?
>
> Otherwise I think the main issue with types that don't seem like they
> can implement Comparable is that they need a means of detecting that
> they've been invalidated; arguably a singly-linked list's indices
> should become unusable if it has been changed, which could be done for
> example by giving the list a mutationCount value that is incremented
> each time it is mutated; indices would take a copy of this value and
> if they don't match, they produce a runtime error. Like so (heavily
> abridged):
>
> 	struct LinkedListIndex<Element> : Comparable {
> 		let mutationCount:Int
> 		var position:Int, node:LinkedListNode<Element>
> 	}
> 	func == <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return lhs.position == rhs.position }
> 	func < <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return lhs.position < rhs.position }
>
> 	class LinkedListNode<Element> {
> 		var element:Element, next:LinkedListNode<Element>?
> 		init(_ element:Element) { self.element = element }
> 	}
>
> 	struct LinkedList<Element> : Indexable {
> 		var mutationCount:Int = 0, head:LinkedListNode<Element>?, tail:LinkedListNode<Element>?
>
> 		typealias Index = LinkedListIndex
> 		var startIndex:Index { return LinkedListIndex(mutationCount: self.mutationCount, position: 0) }
> 		func formIndex(after i:inout Index) {
> 			precondition(i.mutationCount == self.mutationCount, "Invalid index")
> 			i.position += 1
> 			i.node = i.node?.next
> 		}
> 		func index(after i:Index) -> Index { var i = i; self.formIndex(after: &i); return i }
> 		subscript(i:Index) -> Element {
> 			precondition(i.mutationCount == self.mutationCount, "Invalid index")
> 			return i.node!.element
> 		}
>
> 		mutating func append(_ element:Element) {
> 			let node = LinkedListNode(element)
> 			if self.tail == nil { self.head = node; self.tail = node }
> 			else { self.tail.next = node; self.tail = node }
> 			self.mutationCount = self.mutationCount &+ 1
> 		}
> 	}
>
> Please forgive typos/omissions, tried to keep it as short as possible. But yeah, this is essentially how I'd try to implement a linked list, while retaining the Comparable constraint.
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
Dave