Update elements to use NonEmptyArray instead of NonEmpty Array

[milesfrain]

Assuming purescript/purescript-arrays#137 applies here too.
https://pursuit.purescript.org/packages/purescript-quickcheck/6.1.0/docs/Test.QuickCheck.Gen#v:elements

[kl0tl]

Do we really want to do this? Constructing and deconstructing a NonEmpty Array with :| and pattern matching is O(1) but aren’t uncons and cons' (the equivalent operations from Data.Array.NonEmpty) O(n) since they have to copy the tail of the array?

[hdgarrood]

There's a tradeoff here - the advantage of NonEmptyArray is that conversion to or from array is O(1), and that's not true for NonEmpty Array. It's not immediately clear to me which one is preferable here.

[kl0tl]

Test.QuickCheck.Gen.oneOf and Test.QuickCheck.Gen.elements immediately pattern match on their non empty argument, doesn’t that cancel any performance benefit that would be gained by the O(1) conversion of an Array to a NonEmptyArray (since we would have to copy the array tail with uncons instead)?

[JordanMartinez]

doesn’t that cancel any performance benefit that would be gained by the O(1) conversion of an Array to a NonEmptyArray (since we would have to copy the array tail with uncons instead)?

Probably. While one could use an unsafeIndex arr 0, I'm not sure if that would cause other problems later.

[hdgarrood]

We would probably want to adjust their implementations so that they didn’t do that, then. I feel like that ought to be possible but I haven’t looked.

[kl0tl]

This makes some Arbitrary slightly awkward but it was indeed possible to rewrite oneOf, arrayOf1 and elements without the O(n) uncons and cons'!