Performance – slow tail recursive in F #

let rec indicesForStep start blockSize maxSize =
 match start with
 | i when i> maxSize -> []
 | _ -> [for j in start .. ((min (start + blockSize) maxSize)-1) -> j) @ indicesForStep (start + 2 * blockSize) blockSize maxSize

let indicesForStepTail start blockSize maxSize =
 let rec indicesForStepInternal istart accumList =
 match istart with
 | i when i> maxSize -> accumList
 | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize)-1) -> j])
 indicesForStepInternal start []

let indicesForStepTail start blockSize maxSize =
 let rec indicesForStepInternal istart accumList = 
 match istart with
 | i when i> maxSize -> accumList |> List.rev
 | _ -> 
 let acc = 
 [for j in (( min (istart + blockSize) maxSize)-1) .. -1 .. istart -> j] 
 @ accumList
 indicesForStepInternal (istart + 2 * blockSize) acc
 indicesForStepInternal start []< /pre> 
As you can see, this has a shorter list (generated with [...]) as the first parameter of @, on my machine, it has a similarity to the non-tail recursive version Performance. Note that […] understands that the elements are generated in reverse order – so that they can be reversed at the end.
 
You can also use F#seq {..} syntax to better write the entire content. You can avoid the @ operator altogether because it allows you to use yield to generate a single elemet and use yield to perform tail recursive calls! :
 
 
let rec indicesForStepSeq start blockSize maxSize = seq {
 match start with
 | i when i> maxSize -> ()
 | _ -> 
 for j in start .. ((min (start + blockSize) maxSize)-1) do
 yield j
 yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize} 
This is how I wrote it. When calling it, you only need to add Seq.toList to evaluate the entire delay sequence. The performance of this version is similar to the first version.
 Edited through Daniel's correction, the Seq version is actually slightly faster! 

I have an F# function that returns a list of numbers starting from 0 in the mode of skipping n, select n, skip n, select n...the limit is reached. For example, this function of input 2 will return [2,3,6,7,10,11 …].

Initially I implemented it as a non-tail recursive function, as shown below:< /p>

let rec indicesForStep start blockSize maxSize =
 match start with
 | i when i> maxSize -> []
 | _ -> [ for j in start .. ((min (start + blockSize) maxSize)-1) -> j) @ indicesForStep (start + 2 * blockSize) blockSize maxSize

Thinking that tail recursion is desirable, I use The accumulator list reimplements it as follows:

let indicesForStepTail start blockSize maxSize =
 let rec indicesForStepInternal istart accumList =
 match istart with
 | i when i> maxSize -> accumList
 | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize)-1) -> j ])
 indicesForStepInternal start []

However, when I use the parameters 1,1 and 20,000 under Mono (that is, [1,3,5,7 …] should be returned to 20,000) in When running in fsi, the tail recursive version is significantly slower than the first version (12 seconds compared to sub-seconds).

Why the tail recursive version is slower? Is it because the list is connected? Is it a compiler optimization? Did I really implement it recursively?

I also think I should use a higher-order function to do this, but I am not sure how to do it.

As Dave pointed out, the problem is that you are using the @ operator to append the list. This is a more important performance issue than tail recursion. In fact, tail recursion does not really speed up the program (but it makes it suitable for stack overflow Large input).

The reason your second version is slower is that you append a shorter list (list generated with [...]) to a longer list (accumList) This is slower than appending a longer list to a shorter list (because the operation needs to copy the first list).

You can do this by collecting the elements in the accumulator in reverse order and then before returning the result Reverse it to fix it:

let indicesForStepTail start blockSize maxSize =
 let rec indicesForStepInternal istart accumList =
 match istart with
 | i when i> maxSize -> accumList |> List.rev
 | _ -> 
 let acc = 
 [for j in ((min (istart + blockSize) maxSize)-1). . -1 .. istart -> j] 
 @ accumList
 indicesForStepInternal (istart + 2 * blockSize) acc
 indicesForStepInternal start []

As you can see , This has a shorter list (generated using [...]) as the first parameter of @, on my machine, it has similar performance to the non-tail recursive version. Please note that [...] understands the opposite Generate elements in order – so that they can be reversed at the end.

You can also use F#seq {..} syntax to better write the entire content. You can completely avoid the @ operator because it allows You use yield to generate a single elemet and use yield to perform tail recursive calls! :

let rec indicesForStepSeq start blockSize maxSize = seq {
 match start with
 | i when i> maxSize -> ()
 | _ -> 
 for j in start .. ((min (start + blockSize) maxSize)-1) do
 yield j
 yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize} 

This is how I wrote it. When calling it, you only need to add Seq.toList to evaluate the entire delay sequence. The performance of this version is similar to the first version.

Edited through Daniel's correction, the Seq version is actually slightly faster!