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

Consider the type signature of List.fold_left:

('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

List.fold_left takes three arguments.

1. A function.
2. An initial value.
3. A list to iterate over.

List.fold_left @ lists

You're making two mistakes.

First off, this parses as (List.fold_left) @ (lists).

You're looking for List.fold_left (@) lists. But that's still not quite right, because...

You're only passing two arguments, with lists being the initial value, while List.fold_left expects three.

I think that you're looking for something like:

let concat lists = List.fold_left (@) [] lists

Demonstrated:

# let concat lists = List.fold_left (@) [] lists in
  concat [[1;2;3]; [4;5;6]; [7;8;9]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

Runtime complexity

The danger to this approach to concatenating lists is that while it runs in constant stack space since List.fold_left is tail-recursive and @ is (at least as of this edit), it's runtime complexity is O(n²).

concat [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]

Is equivalent to:

(([] @ [1; 2; 3]) @ [4; 5; 6]) @ [7; 8; 9]

This code has to iterate to the end of [1; 2; 3] to generate [1; 2; 3; 4; 5; 6] and then has to iterate to the end of [1; 2; 3; 4; 5; 6] to generate [1; 2; 3; 4; 5; 6; 7; 8; 9].

Now imagine our list of lists had a very large number of lists and each was large. The runtime quickly gets out of control.

Instead we can use ::, which has constant runtime to reduce this to O(n) runtime, as in the following code.

let rec concat = function
  | [] -> []
  | []::tl -> concat tl
  | (x::xs)::tl -> x :: concat (xs :: tl)

Of course, this is not tail-recursive, so it runs in linear stack space, but fortunately tail_mod_cons gives us an easy fix for this.

let[@tail_mod_cons] rec concat = function
  | [] -> []
  | []::tl -> concat tl
  | (x::xs)::tl -> x :: concat (xs :: tl)

Answer 2

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.