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.

Tags:

F#