[swift-evolution] Dropping Comparable requirement for indices

[Haravikk]

> 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 }

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. 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() }
	}

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160707/e1b9f03f/attachment.html>