Can I simplify this recursive concat function using List.fold_left?

Question

I have created a working solution for concat, but I feel that I can reduce this using List.fold_lift.

Here is my current code:

let rec concat (lists : 'a list list) : 'a list =
    match lists with
    | [] -> []
    | hd :: tl -> hd @ concat tl ;;

Here is what I have tried:

let concat (lists : 'a list list) : 'a list =
    List.fold_left @ lists ;;

This gives me the error: This expression has type 'a list list but an expression was expected of type 'a list

I think this is because the return value of list.fold_left gives us a list, but we are feeding it a list of lists so it then returns a list of lists again. How can I get around this without matching?

I was also playing around with List.map but with no luck so far:

let concat (lists : 'a list list) : 'a list =
    List.map (fun x -> List.fold_left @ x) lists ;;

Answer 1

It is possible to write concat as fold_left while avoiding quadractic complexity by switching temporarily to different representation of list

If I have a list l, I can easily lift into an append function:

let to_append l  = fun new_list -> l @ new_list

I can also get back a list from an append function with

let to_list append = append []

And since for any list l, I have to_list @@ to_append l = l, this means that the to_append is one-to-one: it does not lose any information.

Moreover concatenating two appends functions is exactly function composition

let append_concat f g l = f (g l)

Since we are not building yet any concrete list, append_concat has a constant cost (we are delaying the time complexity to the moment where we will call the append function).

We can use this better behavior of append_concat to write a linear concat' function that maps a list of lists to an append function:

let concat' l =
  List.fold_left 
    (fun append l -> append_concat append (to_append l))
    (to_append [] (* aka Fun.id *))
    l

Note that this concat' is not yet building a list, it is building a closure which records the list of append functions to call later.

Building concat from concat' is then a matter of transforming back my append function to a list:

let concat l = to_list (concat' l)

And it is the call of to_list which will have a time complexity equal to the size of the final list.

To check that we got the right complexity, we can test that flattening the following list

let test =
  List.init 1_000_000 
   (fun i ->
     List.init 4 (fun k -> k + 4 * i)
   )
(* this is [[0;1;2;3]; [4;5;6;7]; ... [...; 3_999_999]] *)

with

let flattened = concat test

is nearly instant.