NonEmpty<NonEmpty<C>> doesn't mean the collection has at least 2 values

[RemiBardon]

I really like the safety of NonEmpty. I am writing a fully type-safe geographical library, also providing GeoJSON mapping, and I need to store arrays that have at least four values for example (see RFC 7946, section 3.1.6 for example).

I thought I'd use NonEmpty<NonEmpty<NonEmpty<NonEmpty<[MyType]>>>>, but I was surprised to se it's not how the library works. NonEmpty.swift#L9-L10 shows that the collection is stored as-is, not cut into a head value and a tail Slice.

Is it a conscious choice? Wouldn't it be semantically better to make NonEmpty behave as I thought?

[stephencelis]

Originally, NonEmpty had the following design:

struct NonEmpty<C: Collection>: Collection {
  var head: C.Element
  var tail: C
}

This was changed in #26 for performance, bug-avoidance, and added functionality, to the following:

struct NonEmpty<C: Collection>: Collection {
  var rawValue: C
  // ... validated non-empty via init 
}

But if I'm understanding correctly, your suggestion is something more like the following?

struct NonEmpty<C: Collection>: Collection {
  var head: C.Element
  var tail: Slice<C>
}

This is definitely interesting! In addition to the functionality you mention, it also avoids some of the issues we aimed to address in #26.

The main gotchas I can think of is that the value of head and tail.base[0] may be duplicated, and that they could also diverge.

[RemiBardon]

First, let me apologize for creating an issue instead of a GitHub discussion, I'm not used to discussions.

Originally, NonEmpty had the following design

Yeah, I remember you talking about it, and I'm used to Haskell's head and tail, so it made sense.

This was changed in #26 for performance, bug-avoidance, and added functionality

I was aware of this, but still surprised by the semantic of NonEmpty<NonEmpty<C>> 🙃

But if I'm understanding correctly, your suggestion is something more like the following?

struct NonEmpty<C: Collection>: Collection {
  var head: C.Element
  var tail: Slice<C>
}

Yes, something like this, it would make more sense (at least to me).

The main gotchas I can think of is that the value of head and tail.base[0] may be duplicated, and that they could also diverge.

Oh yeah, good catch! But couldn't this be simply fixed by a computed head property? The performance drawbacks wouldn't be that big (compared to the features it would allow) 🤔

[RemiBardon]

Actually, we'd need also a setter to change tail.base[0], which means we'd have:

struct NonEmpty<C: Collection>: Collection {
  var head: C.Element {
    get { tail.base[0] }
    set { tail.base[0] = newValue }
  }
  var tail: Slice<C>
}

[stephencelis]

Oh yeah, good catch! But couldn't this be simply fixed by a computed head property? The performance drawbacks wouldn't be that big (compared to the features it would allow) 🤔

Good point! I think there's still some potential trickiness around the tail slice ever changing its indices, but this could hopefully be mitigated. We'll have to explore this soon 😄

[RemiBardon]

Do you want me to start a pull request? I can implement my thoughts and see if it works 👍🏻

[RemiBardon]

You didn't answer, so I forked and tried to implement my idea.

The first two problems I have are Cannot convert value of type 'Int' to expected argument type 'Collection.Index' and Cannot assign through subscript: subscript is get-only.

The first one can be avoided by using .first!, but I couldn't find a way to avoid the second issue, while keeping compatibility with all Swift.Collections 😕

[RemiBardon]

I also thought about other features that could be added at the same time.

Basically, NonEmpty<NonEmpty<C>> would mean we have at least two values, but the API would only expose first: C.Element, not second.

What we could do is something like this (pseudo Swift code)

extension NonEmpty<NonEmpty<C>> {
    var second: C.Element { tail.first }
}
extension NonEmpty<NonEmpty<NonEmpty<C>>> {
    var third: C.Element { tail.second }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>> {
    var fourth: C.Element { tail.third }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>> {
    var fifth: C.Element { tail.fourth }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>> {
    var sixth: C.Element { tail.fifth }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>> {
    var seventh: C.Element { tail.sixth }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>>> {
    var eighth: C.Element { tail.seventh }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>>>> {
    var ninth: C.Element { tail.eighth }
}
extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>>>>> {
    var tenth: C.Element { tail.ninth }
}

Now we can safely access indexes 1 to 10, but not above. I had an idea though (still pseudo Swift code):

extension NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>>>>>> {
    var drop10: NonEmpty<C> { get }
}

This way, we can do myCollection.drop10.first to get the 11th index safely, and myCollection.drop10.drop10.fourth to get the 24th index safely 🥳

[RemiBardon]

Another problem I stumbled upon is the actual failing initializer (init?) making things very verbose:

let myOptionalCollectionWithAtLeast4Elements = NonEmpty(rawValue: elements)
    .flatMap(NonEmpty.init(rawValue:))
    .flatMap(NonEmpty.init(rawValue:))
    .flatMap(NonEmpty.init(rawValue:))

I don't know why you chose init? over init() throws (I admit, I haven't searched) 🤔
We could create a throwing initializer (init() throws), keeping init? as a convenience initializer using try?.

The throwing initializer would allow avoiding optional chaining, like so:

let myOptionalCollectionWithAtLeast4Elements = try? NonEmpty(NonEmpty(NonEmpty(NonEmpty(elements))))

[RemiBardon]

If you accept my previous two propositions (about myCollection.drop10.drop10.fourth and init() throws), I thought about one more improvement:

typealias AtLeast2<C> = NonEmpty<NonEmpty<C>>
extension AtLeast2 {
    var second: C.Element { get }
}
typealias AtLeast3<C> = NonEmpty<NonEmpty<NonEmpty<C>>>
extension AtLeast3 {
    var third: C.Element { get }
}
// ...
typealias AtLeast10<C> = NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>>>>>>>>
extension AtLeast10 {
    var tenth: C.Element { get }
}

extension NonEmpty {
    static func atLeast2<C>(_ c: C) -> AtLeast2<C>
    static func atLeast3<C>(_ c: C) -> AtLeast3<C>
    // ...
    static func atLeast10<C>(_ c: C) -> AtLeast10<C>
}

AtLeastN are type aliases, and require a static func in NonEmpty, because making it structs with initializers would require redefining Collection conformances and would just be a pain when making changes in the library.

This would remove the necessity to use NonEmpty<NonEmpty<NonEmpty<NonEmpty<C>>>> around, reducing it to AtLeast4<C>.

It would also also replace try NonEmpty(NonEmpty(NonEmpty(NonEmpty(collection)))) by try NonEmpty.atLeast4(collection).

Finally, like myCollection.drop10.drop10.fourth, we could use the AtLeast10<AtLeast10<AtLeast4<C>>> type (which is a huge improvement).