[RFC FS-1036 Discussion] Consistent slicing

[charlesroddie]

Discussion for https://github.com/fsharp/fslang-design/blob/master/FSharp.Core-4.4.3.0/FS-1036-consistent-slicing.md

[syeerzy]

thank you.

i found there's no test for list in https://github.com/Microsoft/visualfsharp/blob/master/tests/fsharp/core/array/test.fsx
as you said.

the only tests for list type slicing are here:
https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core.Unittests/FSharp.Core/Microsoft.FSharp.Collections/ListType.fs

let lst = [1;2;3;4;5;6]
    .......
    CheckThrowsIndexOutRangException((fun _ -> lst.[7..] |> ignore))        
    CheckThrowsIndexOutRangException((fun _ -> lst.[.. -1] |> ignore))
    .......
    Assert.AreEqual(lst.[-3..-4], ([]: int list))          // !!!!!!!!!  <------  ?
    CheckThrowsIndexOutRangException((fun _ -> lst.[-4..-3] |> ignore)) 

[charlesroddie]

Thanks for finding the tests.

lst.[-3..-4]=[] makes sense . This RFC does not change lst.[i..j], which is not problematic. See the RFC PR for a definition of lst.[i..j].

[cartermp]

Closing old discussion - the feature is implemented and shipped

[cartermp]

Re-opening as per "discovery" (🙃 ) that this isn't completed

[cartermp]

Continuing from fsharp/fslang-suggestions#358

(Paraphrasing, so please correct if this is not accurate)

@charlesroddie makes the claim that x.[0..-1] must be equal to [] (or "", etc.) because it is a base case for extracting the empty set from a given collection in a way that is consistent with how F# end index are inclusive in range expressions. This is mathematically sound. The Python/C# 8 behavior does not do this, because the end index is exclusive, so getting [] is done with x[0:0] or x[0..0].

I find that the notion that x.[0..-1] has any meaning other than throwing an exception to be problematic.

• Failing a different definition for the end index of a range expression, for x.[a..b], b is a value that represents an index in the collection when taking a slice
• x.[-1] is exceptional behavior today, because there is no such thing is a negative index of a set in .NET

In fact, the current implementation feels broken:

> let lst = [1; 2];;
val lst : int list = [1; 2]

> lst.[0..(-1000)];;
val it : int list = []

It could be argued that anything below 0 for the end index means you'll get [], though I'd probably disagree with that. Perhaps this is just a bug?

At any rate, while we're consistent with one definition, it seems to me that we're inconsistent with the idea that getting the value from the negative index of a collection is exceptional behavior.

[charlesroddie]

Definition 1: The current definition of x.[a..b]

Take the set {n:a≤n≤b}, order it as a list, and look up the elements of that list.

An imperative definition with the same result: [ let mutable i = a; while i <= b do yield i ]

Definition 2: An alternate inductive definition showing the base case:

x.[a .. a-1] = []
x.[a..b] = x.[a] :: x.[a+1..b]

let rec slice x (a, b) =
    if b = a - 1 then [] else x.[a] :: slice x (a + 1, b)

x.[0 .. -1]=[] is unambiguous while x.[0 .. -1000] is definition-dependent

The definitions agree whenever definition 2 applies: when a ≤ b+1. Outside this range definition 2 cannot go further (probably fails) and definition 1 gives [].

In particular both definitions agree on x.[0..-1]: this does not involve looking up any elements, and should succeed and equal [] regardless of whether x.[-1] is defined or not.

x.[0.. -1000] equals [] by the first definition and fails on the second definition because it's not possible to add elements to a list and end up with the empty list.

@cartermp 's definition

The same as 1 and 2 but with the assertion that a≤b.

This assertion may feel comfortable because it guarantees that a and b are looked up. It corresponds to a notion of "inclusive end case must include the end".

Inclusivity and exclusivity

If F# had exclusive end cases the first definition would change to {n:a≤n<b} and the second to x.[a .. a] = [] but nothing would change in practice.

No-one disagrees about how things should be defined in exclusive-end ranges for a≤b. The mathematical properties and the property that the end is excluded line up.

So really this is an argument about: is taking "inclusive end includes the end" as absolute more important than the having the mathematically appropriate base case which extends the x.[a+1..b] = x.[a] :: x.[a+1..b] property as far as possible.

If inclusive-end syntax is given by definition 1 or 2, then it has the same capability as exclusive-end syntax and an exact correspondence (up to a difference of 1 in b). While if the restriction a≤b is imposed then it has less functionality than exclusive-end syntax and cannot return empty sequences.

Valid indices: a red herring

x.[-1] is exceptional

An attempt to look up a value for which a list is not defined should fail. This is a red herring though since x.[0 .. -1]=[] would not involve a look up even if x.[-1] were defined (e.g. non-zero based). x.[1..0]=[] has the same logic and doesn't involve negative numbers.

[cartermp]

So really this is an argument about: is taking "inclusive end includes the end" as absolute more important than the having the mathematically appropriate base case which extends the x.[a+1..b] = x.[a] :: x.[a+1..b] property as far as possible.

a <= b (with the extension that they are positive) is indeed more important than having a mathematically appropriate base case for this specific mathematical system, yes. There is no utility in extracting an empty slice from something by giving arbitrary negative indices, and this does not collide with the notion that negative indices are undefined on .NET.

[charlesroddie]

this does not collide with the notion that negative indices are undefined on .NET

See above comment on valid indices.

There is no utility in extracting an empty slice from something by giving arbitrary negative indices

This is not true. The difference of 1 in the definition of the second number between inclusive-end and exclusive-end languages does not affect the utility of extracting empty slices. Or do you think 0..0 should fail in exclusive-end languages too?

The utility of extracting an empty sequence is enormous (and similar to the utility of using trivial base cases in other contexts). Slicing would be completely broken without it.

Here is code that should succeed but would fail if your version of slicing were used and require hacky workarounds. (Typical of choosing the wrong base case.)

// Not slicing but the same idea
// prints "hello" n times, for 0<=n
for x in 1..n do printf "hello"

// should (structurally) equal l for any list/array/seq l
l.[0 .. (l.Length-1)]

// does what the name says
let replaceFirstAWithB l =
    match l |> List.tryFindIndex ((=) 'A') with
    | Some n -> l.[.. n-1] @ ['B'] @ l.[n+1 ..]
    | None -> l

// Parses an string of the form A*B where A and B are integers.
// Should return `Result.Error "Could not parse an integer"` given the input "36*"
let parseInt s = match System.Int32.TryParse s with (true, r) -> Some r | _ -> None
let parseAndCalculateIntProduct (s:string) =
    match s |> Seq.tryFindIndex ((=) '*') with
    | Some n ->
        match parseInt s.[0 .. n-1], parseInt s.[n+1 .. (s.Length-1)] with
        | Some a, Some b -> Result.Ok(a*b)
        | _ -> Result.Error "Could not parse an integer"
    | None -> Result.Error "* not found"

In fact I would expect that most slicing in practice where the start or end case is not a specified constant* would fail.

The fundamental problem is that getting the items with index <= i and items with index >= i becomes hard, because it cannot be done with slicing any more. Moreover many users would expect slicing to work for this purpose (.[..i] and .[i..]) and get unexpected runtime failures.

*(Naturally it would be rare to write l.[0..-1] just as it would be rare to write x+0 or 0! or x^0 or \sum_{i=0}^{-1}f(i) or l@[] but these need to be defined right or else code/mathematics will break/become extremely unwieldy.)

[cartermp]

I spent some time playing around with a different GetSlice implementation for lists, and I came to two conclusions that are at odds with one another:

• Supporting any value at the end index that is negative still makes no sense, as it seems to violate the intuition that a slice is extracted from two positions in the set - negative indices, or those which could be negative, seem to violate that every time I use it
• Composition of lists and strings when combined with slicing is difficult without this. While I don't personally see this as an issue as you'd still need to account for base cases for types that don't compose as easily, I could see this as being important to other people

So, perhaps begrudgingly, I'm willing to accept this as the definition and move forward. The fact that changing it to an error case would involve a breaking change pushes this over the edge for me. It still will be hard not to see this as an ergonomic wart for others who don't see negative indices as unrelated to slicing.

This is also possible:

> arr;;                                                                                                                                                                                
val it : int [] = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

> arr.[3..2];;
val it : int [] = [||]

> str;;
val it : string = "Hello"

> str.[3..2];;
val it : string = "" 

So it seems the definition of a slice x.[a..b] is (at least, aspirationally):

• Invalid for a < 0, a > x.length-1, or b > x.length-1
• [] for anyb < a not in violation of the previous point
• The subset of x between a and b (inclusive)

I also feel that this is wrong, but since it's been shipped for arrays, strings, and lists I think the ship has sailed on this one.

[nelson-wu]

Here's my take on this:

Make Slicing Consistent Again

After dotnet/fsharp#3475 we got
L.[x..] = L.[x..(L.Length -1 )]
L.[..y] = L.[0..y]
However we still have some problems.

Assuming we have a list L with lower bound a and upper bound b, then:
L = { L[a], L[a+1] ... L[b-1], L[b] }

Our current slicing behavior in F# looks like:

L.[x..y]	x < a	a <= x <= b	x > b
y < a	if x > y [] else Error	[]	[]
a <= y <= b	Error	if x > y [] else { L[x] .. L[y] }	[]
y > b	Error	Error	if x > y [] else Error

The current behavior in C# .NET preview is:

L[x..y]	x < a	a <= x <= b+1	x > b+1
y < a	Error	Error	Error
a <= y <= b+1	Error	{ L[x] .. L[y-1] }	Error
y > b+1	Error	Error	Error

The current behavior in Python is:

L[x:y]	a <= x <= b+1	x > b+1
a <= y <= b+1	if x > y [] else { L[x] .. L[y-1] }	[]
y > b+1	{ L[x] .. L[b] }	[]

(Note: We can't have x < a and y < a cases because Python negative indices mean something else)

Problem

As you can see from the example above the slicing behavior in F# is a lot more confusing than C# or Python. Sometimes when indexes are out of bounds you get [], sometimes you get Error, and sometimes you get either.

C# disallows any out of bound indexes and Python just takes L[x:y] = L[x:min(y, b)] and [] if the bounds don't make sense. This is much easier to create a mental model of.

What I think the solution should be:

L.[x..y]	x < a	a <= x <= b	x > b
y < a	[]	[]	[]
a <= y <= b	{ L[a] .. L[y] }	if x > y [] else { L[x] .. L[y] }	[]
y > b	{ L[a] .. L[b] }	{ L[x] .. L[b] }	[]

This is pretty much equivalent to L.[x..y] = L.[max(x, a)..min(y, b)] and [] otherwise.

Why?

• The legacy behavior has been L.[0..(-1)] = [], so we don't want to change that to Error all of a sudden.
• This would work with @charlesroddie 's concatenation and recursive cases.
• For people who are doing calculations on arrays of numbers (perhaps ML workloads) your life would be easier as you wouldn't have to explicitly check for bounds.
• This would bring F# more in line with python and make it more accessible for python users.
• It's much more clearer and consistent.

Some of the disadvantages are:

• We'd change the behavior for cases like L.[0..99999] and L.[-1..0] where they would become valid. If users are catching that exception and performing logic based on that we'd break their code (they shouldn't be doing so anyways).
• If you accidentally access an out-of-bounds slice the compiler's not going to warn you about it.

From-the-end slicing

I've talked to @KevinRansom about this and we can't use L.[..-1] = { L[a] .. L[b-1] } because .NET arrays can be initialized with whatever starting index you want including negative numbers 😨. I think using the ^ symbol like in C# 8.0 System.Range would be a good alternative, and we could just convert L.[x..^y] to L.[x..(L.Length-y-1) (-1 since our slices are end-inclusive). Note that this would also require L.[0..(-1)] = [], which is valid in the suggested version.

@dsyme @KevinRansom @cartermp what do you think?

[KevinRansom]

I think this makes sense. It seems to replace some runtime slicing failures and compile time slicing failures with empty slices instead. Here is an F# API for creating Multi-dimensional arrays that have non zero bases -> https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/array2d.createbased%5b't%5d-function-%5bfsharp%5d Wierdly enough the dotnet framework doesn’t seem to provide an API for creating a single dimensioned array that is not zero based. This is the dotnet API for it -> https://docs.microsoft.com/en-us/dotnet/api/system.array.createinstance?view=netframework-4.8#System_Array_CreateInstance_System_Type_System_Int32___System_Int32___ Anchoring from the end using ^ seems fine to me, however, we probably would need to modify the signature for the slicing helper function to include a flag Indicating anchored at end. GetSlice(x : int, y1 : int option, y2 : int option, anchoredfromend:bool

[charlesroddie]

F# is consistent

There are three consistent slicing definitions:

	l.[x..y]
Strict	if x <= y+1 then [x..y] |> List.map l.Item else failwith "invalid range"
Intermediate	[x .. y] |> List.map l.Item
Forgiving	[ for i in [x .. y] do if isValidIndex l i then yield l.[i] ]

(Here [x..y] is the set {n:x≤n≤y}, ordered as a list: the current F# definition.)

F# is currently Intermediate.
Python is Forgiving when restricted to positive indices. Negative numbers hacky.
OCaml Array.sub (adjusted for length vs. end) is Strict
C# is stricter than Strict: in addition to looking up [x..y] and requiring x <= y+1 it also looks up x and y and ignores the results. Insane.

Intermediate is better than Forgiving

@nelson-wu 's suggestion is to go from Intermediate to Forgiving

On undisputably valid ranges (x <= y+1 and [x..y] all valid indices), all three options give the same results.

Moving to Forgiving will lead to a significantly less safe language. Indices are easy to get wrong. Even off by one errors are common enough to get their own category. When slices are incorrectly specified, it is much better that they fail than succeed, leading to later unexpected output or failures.

So I am against this change.

In order to justify the change, examples will need to be given of where a user would naturally write a range, which we should consider good, and which currently fails.

[cartermp]

@nelson-wu I think your proposal makes sense and I like it. Note that L also needs to stand for arrays (1D and 2D) and strings in addition to list, since currently the existing list behavior does not exist for them:

I think I'm now generally more in favor of being weaker here, after doing more numeric work in Python and seeing how convenient it is compared to F#. Much of that is due to more features than we have, but this certainly would move the needle.

Regarding negative indicies, I agree that ^ is the character we should pick

Regarding the signature of GetSlice - I think that's a reasonable signature. We'll just have to teach the compiler to understand that overload.

[dsyme]

I'm struggling with the phenomenon where

1. I read @nelson-wu 's RFC and think it's 100% ok
2. I read @charlesroddie 's reasons for explaining why we don't want to make a change here and think it's 100% ok

Help!

[cartermp]

@dsyme if it helps, @nelson-wu has a fantastic example here: https://github.com/fsharp/fslang-design/blob/13a043d23db9ca847f70ba5f21cfe7238c349639/FSharp.Core-4.4.3.0/FS-1036-consistent-slicing.md#sample-use-case

[charlesroddie]

@nelson-wu 's example of splitting arbitrary images into blocks of 3 is valid.

An indecisive option @dsyme would be to introduce a new methods for tolerant slices to some or all collections. Array.SafeSlice etc.. Advantages: Literally splitting images not divisible by 3 into blocks of 3 is not possible, so the logic of the implementation should be explicit, and using a different slicing method with an explicit name does that. And it doesn't interfere with existing slicing, so bad code fails more often at the right place. Disadvantages: more code in FSharp.Core and a larger API surface.

[dsyme]

@nelson-wu Let's open the additional alterations as a separate RFC, as RFC FS-1036 is done and dusted

Call it "tolerant slicing" I guess

[nelson-wu]

@dsyme Ah that's reasonable. I'll break it out into its own RFC.