Use ListCollector on List operations to improve perf

[TheAngryByrd]

*Is your feature request related to a problem? Please describe.

https://twitter.com/dsymetweets/status/1494424576834605064

Describe the solution you'd like

TODO

Describe alternatives you've considered

Not doing this

Additional context Add any other context or screenshots about the feature request here.

[TheAngryByrd]

Additionally, figure out how to utilize InlineIfLambda in the list module as with the current implementation it's not possible.

error FS1113: The value 'traverseResultM' was marked inline but its implementation makes use of an internal or private function which is not sufficiently accessible 

[TheAngryByrd]

Need to consider the error paths as well: https://github.com/demystifyfp/FsToolkit.ErrorHandling/issues/178#issue-1226538645

[TheAngryByrd]

Results

let rec private traverseResultM' (state: Result<_, _>) (f: _ -> Result<_, _>) xs =
    match xs with
    | [] -> state |> Result.map List.rev
    | x :: xs ->
        let r =
            result {
                let! y = f x
                let! ys = state
                return y :: ys
            }

        match r with
        | Ok _ -> traverseResultM' r f xs
        | Error _ -> r

  let rec private traverseResultA' state f xs =
      match xs with
      | [] -> state |> Result.map List.rev |> Result.mapError List.rev
      | x :: xs ->
          let fR : Result<'a, 'b> = f x 

          match state, fR with
          | Ok ys, Ok y -> traverseResultA' (Ok(y :: ys)) f xs
          | Error errs, Error e -> traverseResultA' (Error(e :: errs)) f xs
          | Ok _, Error e -> traverseResultA' (Error [e]) f xs
          | Error e, Ok _ -> traverseResultA' (Error e) f xs

Method	Categories	entries	Mean	Error	StdDev	Median	Gen 0	Gen 1	Allocated
List_traverseResultM_normal_allOks	traverseResultM	1	80.63 ns	1.604 ns	1.647 ns	80.97 ns	0.0172	-	144 B
List_traverseResultM_normal_allErrors	traverseResultM	1	56.14 ns	1.595 ns	4.703 ns	54.97 ns	0.0134	-	112 B
List_traverseResultM_normal_half	traverseResultM	1	56.79 ns	1.636 ns	4.824 ns	56.99 ns	0.0134	-	112 B
List_traverseResultM_normal_allOks	traverseResultM	10	344.26 ns	6.885 ns	7.929 ns	340.66 ns	0.1240	-	1,040 B
List_traverseResultM_normal_allErrors	traverseResultM	10	147.33 ns	1.256 ns	1.049 ns	147.02 ns	0.0477	-	400 B
List_traverseResultM_normal_half	traverseResultM	10	142.31 ns	1.836 ns	1.534 ns	142.20 ns	0.0477	-	400 B
List_traverseResultM_normal_allOks	traverseResultM	100	2,830.22 ns	26.658 ns	23.631 ns	2,824.42 ns	1.1559	0.0267	9,680 B
List_traverseResultM_normal_allErrors	traverseResultM	100	928.40 ns	13.792 ns	12.901 ns	925.54 ns	0.3910	0.0038	3,280 B
List_traverseResultM_normal_half	traverseResultM	100	942.75 ns	16.422 ns	14.557 ns	943.24 ns	0.3910	0.0038	3,280 B
List_traverseResultM_normal_allOks	traverseResultM	1000	29,259.49 ns	550.551 ns	514.986 ns	29,405.35 ns	11.4746	2.1362	96,080 B
List_traverseResultM_normal_allErrors	traverseResultM	1000	9,055.85 ns	158.835 ns	148.574 ns	9,028.45 ns	3.8300	0.3815	32,080 B
List_traverseResultM_normal_half	traverseResultM	1000	9,060.88 ns	152.808 ns	142.937 ns	9,029.95 ns	3.8300	0.3815	32,080 B
List_traverseResultA_normal_allOks	traverseResultA	1	55.47 ns	1.130 ns	1.057 ns	55.11 ns	0.0172	-	144 B
List_traverseResultA_normal_allErrors	traverseResultA	1	59.40 ns	1.134 ns	1.060 ns	59.57 ns	0.0172	-	144 B
List_traverseResultA_normal_half	traverseResultA	1	54.00 ns	0.649 ns	0.576 ns	54.04 ns	0.0172	-	144 B
List_traverseResultA_normal_allOks	traverseResultA	10	296.93 ns	5.956 ns	6.117 ns	295.76 ns	0.1240	-	1,040 B
List_traverseResultA_normal_allErrors	traverseResultA	10	313.03 ns	3.709 ns	3.469 ns	312.14 ns	0.1240	-	1,040 B
List_traverseResultA_normal_half	traverseResultA	10	250.58 ns	4.663 ns	4.134 ns	250.23 ns	0.0858	-	720 B
List_traverseResultA_normal_allOks	traverseResultA	100	2,803.16 ns	89.362 ns	263.486 ns	2,715.78 ns	1.1559	0.0267	9,680 B
List_traverseResultA_normal_allErrors	traverseResultA	100	2,660.38 ns	51.943 ns	55.578 ns	2,649.17 ns	1.1559	0.0267	9,680 B
List_traverseResultA_normal_half	traverseResultA	100	2,106.10 ns	40.534 ns	41.625 ns	2,102.22 ns	0.7744	0.0114	6,480 B
List_traverseResultA_normal_allOks	traverseResultA	1000	25,830.87 ns	511.017 ns	699.485 ns	25,540.17 ns	11.4746	2.1057	96,080 B
List_traverseResultA_normal_allErrors	traverseResultA	1000	26,560.92 ns	517.764 ns	1,279.785 ns	26,083.49 ns	11.4746	2.1057	96,080 B
List_traverseResultA_normal_half	traverseResultA	1000	21,864.32 ns	617.860 ns	1,812.077 ns	21,105.21 ns	7.6599	0.9766	64,080 B

---

let traverseResultM f xs = 
  let mutable oks = ListCollector()
  let mutable hasError = false
  let mutable error = Unchecked.defaultof<_>
  use i = (xs : seq<_>).GetEnumerator()
  while not hasError && i.MoveNext() do
      match f i.Current with
      | Ok o -> oks.Add o
      | Error e ->
          hasError <- true
          error <- Error e
  if hasError then error
  else
      Ok (oks.Close())

let traverseResultA f xs =
  let mutable oks = ListCollector()
  let mutable hasErrors = false
  let mutable errors = ListCollector()
  for x in xs do
      match f x with
      | Ok o -> 
          oks.Add o
      | Error e -> 
          hasErrors <- true
          errors.Add e
  if hasErrors then Error (errors.Close())
  else Ok (oks.Close())

Method	Categories	entries	Mean	Error	StdDev	Median	Gen 0	Gen 1	Gen 2	Allocated
List_traverseResultM_normal_allOks	traverseResultM	1	73.93 ns	1.043 ns	0.871 ns	74.02 ns	0.0219	-	-	184 B
List_traverseResultM_normal_allErrors	traverseResultM	1	63.33 ns	1.672 ns	4.903 ns	61.27 ns	0.0181	-	-	152 B
List_traverseResultM_normal_half	traverseResultM	1	60.58 ns	1.043 ns	0.925 ns	60.64 ns	0.0181	-	-	152 B
List_traverseResultM_normal_allOks	traverseResultM	10	330.38 ns	4.507 ns	3.996 ns	329.39 ns	0.0906	-	-	760 B
List_traverseResultM_normal_allErrors	traverseResultM	10	150.83 ns	2.254 ns	1.882 ns	150.81 ns	0.0525	-	-	440 B
List_traverseResultM_normal_half	traverseResultM	10	155.55 ns	1.771 ns	1.657 ns	155.22 ns	0.0525	-	-	440 B
List_traverseResultM_normal_allOks	traverseResultM	100	2,591.03 ns	49.751 ns	46.538 ns	2,588.95 ns	0.7782	0.0191	-	6,520 B
List_traverseResultM_normal_allErrors	traverseResultM	100	958.06 ns	13.540 ns	12.666 ns	962.58 ns	0.3967	0.0038	-	3,320 B
List_traverseResultM_normal_half	traverseResultM	100	948.14 ns	13.554 ns	12.678 ns	946.82 ns	0.3967	0.0038	-	3,320 B
List_traverseResultM_normal_allOks	traverseResultM	1000	27,210.93 ns	541.513 ns	1,030.285 ns	27,376.24 ns	7.6599	1.5869	-	64,120 B
List_traverseResultM_normal_allErrors	traverseResultM	1000	9,923.25 ns	192.106 ns	262.956 ns	9,943.92 ns	3.8300	0.3815	-	32,120 B
List_traverseResultM_normal_half	traverseResultM	1000	9,864.01 ns	197.151 ns	276.378 ns	9,904.34 ns	3.8300	0.3815	-	32,120 B
List_traverseResultA_normal_allOks	traverseResultA	1	72.97 ns	1.215 ns	1.194 ns	72.96 ns	0.0219	-	-	184 B
List_traverseResultA_normal_allErrors	traverseResultA	1	72.79 ns	0.803 ns	0.751 ns	72.77 ns	0.0219	-	-	184 B
List_traverseResultA_normal_half	traverseResultA	1	74.15 ns	0.730 ns	0.609 ns	74.14 ns	0.0219	-	-	184 B
List_traverseResultA_normal_allOks	traverseResultA	10	324.74 ns	4.422 ns	3.920 ns	323.77 ns	0.0906	-	-	760 B
List_traverseResultA_normal_allErrors	traverseResultA	10	320.09 ns	3.663 ns	3.248 ns	318.45 ns	0.0906	-	-	760 B
List_traverseResultA_normal_half	traverseResultA	10	324.87 ns	5.445 ns	5.093 ns	323.50 ns	0.0906	-	-	760 B
List_traverseResultA_normal_allOks	traverseResultA	100	2,534.54 ns	29.257 ns	25.936 ns	2,527.59 ns	0.7782	0.0191	-	6,520 B
List_traverseResultA_normal_allErrors	traverseResultA	100	2,565.66 ns	26.097 ns	24.411 ns	2,566.93 ns	0.7782	0.0191	0.0038	6,520 B
List_traverseResultA_normal_half	traverseResultA	100	2,630.81 ns	41.312 ns	38.643 ns	2,627.16 ns	0.7782	0.0153	-	6,520 B
List_traverseResultA_normal_allOks	traverseResultA	1000	27,917.00 ns	548.738 ns	673.899 ns	27,901.96 ns	7.6599	1.5869	0.0305	64,120 B
List_traverseResultA_normal_allErrors	traverseResultA	1000	27,760.40 ns	513.921 ns	480.722 ns	27,932.28 ns	7.6599	1.6174	-	64,120 B
List_traverseResultA_normal_half	traverseResultA	1000	28,984.26 ns	569.903 ns	903.927 ns	28,740.55 ns	7.6294	1.2817	-	64,120 B

Conclusions

The recursive style is faster but creates more memory usage while the mutable ListCollector is slower but less memory intensive.

[TheAngryByrd]

Going to close this as probably better to be faster.