Slice like functionality from a List in F#

Question

With an array let foo = [|1;2;3;4|] I can use any of the following to return a slice from an array.

foo.[..2] 
foo.[1..2] 
foo.[2..]

How can I do the same thing for List let foo2 = [1;2;3;4]? When I try the same syntax as the array I get error FS00039: The field, constructor or member 'GetSlice' is not defined.

What's the preferred method of getting a subsection of a List and why aren't they built to support GetSlice?

Answer 1

What's the preferred method of getting a subsection of a List and why aren't built to support GetSlice?

Let's make the last question first and the first question last:

Why lists don't support GetSlice

Lists are implemented as linked lists, so we don't have efficient indexed access to them. Comparatively speaking, foo.[|m..n|] takes O(n-m) time for arrays, an equivalent syntax takes O(n) time on lists. This is a pretty big deal, because it prevents us from using slicing syntax efficiently in the vast majority of cases where it would be useful.

For example, we can cut up an array into equal sized pieces in linear time:

let foo = [|1 .. 100|]
let size = 4
let fuz = [|for a in 0 .. size .. 100 do yield foo.[a..a+size] |]

But what if we were using a list instead? Each call to foo.[a..a+size] would take longer and longer and longer, the whole operation is O(n^2), making it pretty unsuitable for the job.

Most of the time, slicing a list is the wrong approach. We normally use pattern matching to traverse and manipulate lists.

Preferred method for slicing a list?

Wherever possible, use pattern matching if you can. Otherwise, you can fall back on Seq.skip and Seq.take to cut up lists and sequences for you:

> [1 .. 10] |> Seq.skip 3 |> Seq.take 5 |> Seq.toList;;
val it : int list = [4; 5; 6; 7; 8]

Answer 2

F# 4.0 will allow slicing syntax for lists (link).

Rationale is here:

The F# list type already supports an index operator, xs.[3]. This is done despite the fact that lists are linked lists in F# - lists are just so commonly used in F# that in F# 2.0 it was decided to support this.

Since an index syntax is supported, it makes sense to also support the F# slicing syntax, e.g. xs.[3..5]. It is very strange to have to switch to an array type to use slicing, but you don't have to make that switch for indexing.

Still, Juliet answer, saying that, most of the time slicing a list is the wrong approach, still holds true. So be wise when using this feature.