How to make a list of lists into single list F#
Depending on the implementation of List.concat it could be highly inefficient. if it is implemented with the naive approach it will use the naive way for a single appending. for the simple case: assume that we got two list xs ys we wish to append together.
then the implementation would be
let rec append =
function
| [], ys -> ys
| xs, [] -> xs
| x::xs, y::ys -> append(x :: append (xs,[y]), ys)
This is the most inefficient implementation there is, another implementation will simple replace the last case return with
x::append(xs,y::ys)
Both has O(n) running time. but the last will have a smaller konstant k (k*n).
The most effecient way with 2*k*n run time are given below. where n is the number of elements, and k is the kost of concatenating a single element to a list.
let collapse lst =
let rec help acc =
function
| [] -> // conversion point
List.rev acc
| (x :: []) :: xss -> // singleton case
help (x :: acc) xss
| (x :: xs) :: xss -> // general case
help (x :: acc) (xs :: xss)
help [] lst // return
In general, don't trust libraries when it comes to efficiency, and be aware that those who make them are just humans as you, so there can be a lot of bugs.
List.concat LL
Will do what you want. The X.concat family of functions concatenate any sequence of the collection X to a single X where X may be a List
, Array
, Seq
or even a String
with a given separator.