functional-programmingocaml

# Flattening a Nested List in OCaml

I'm doing problem 7 of the OCaml exercises. It basically asks given a nested list as defined:

``````type 'a node =
| One of 'a
| Many of 'a node list
``````

Write a function function `flatten` that flattens it:

``````assert (
flatten [ One "a"; Many [ One "b"; Many [ One "c"; One "d" ]; One "e" ] ]
= [ "a"; "b"; "c"; "d"; "e" ])
``````

The solution provided by the website is as follows:

``````let flatten list =
let rec aux acc = function
| [] -> acc
| One x :: t -> aux (x :: acc) t
| Many l :: t -> aux (aux acc l) t
in
List.rev (aux [] list)
;;
``````

I'm wondering why they do `x :: acc` and then reverse the list instead of `acc @ [x]` which would avoid the need to reverse the list at the end?

Solution

• How does `@` work? Well, let's define it.

``````let rec (@) lst1 lst2 =
match lst1 with
| [] -> lst2
| x::xs -> x :: (xs @ lst2)
``````

So, in order to append one list to another, we have to iterate over all of the first list. If we do this within a loop, as that first list gets longer, it takes longer to get to the end of it. In big-O notation, this has O(n^2) or "quadratic" performance. Fine for small sample sizes, but prohibitive for large sample sizes.

However, `::` occurs in constant time. It doesn't matter how big the list is, it will always take the same amount of time to cons a value onto the front of it. If we do that in a loop, we get O(n) or "linear" performance.

Reversing a list also works in linear time. Is it costly to run two linear time operations? Certainly more so that running one, but consider two times n vs. n squared:

n 2n n^2
0 0 0
1 2 1
2 4 4
3 6 8
4 8 16
100 200 10,000
10,000 20,000 100,000,000
1,000,000 2,000,000 1,000,000,000,000

An additional note: the implementation of `flatten` shown by the OP which utilizes `::` is not tail-recursive. The following would be:

``````let flatten lst =
let rec aux lst to_process acc =
match lst, to_process with
| [], [] -> acc
| [], _ -> aux to_process [] acc
| (One v)::xs, _ -> aux xs to_process (v :: acc)
| (Many lst')::xs, _ -> aux lst' (xs @ to_process) acc
in
List.rev @@ aux lst [] []
``````

Following the evaluation of your sample data:

``````flatten [One "a"; Many [One "b"; Many [One "c"; One "d"]; One "e"]]
aux [One "a"; Many [One "b"; Many [One "c"; One "d"]; One "e"]] []        []
aux [Many [One "b"; Many [One "c"; One "d"]; One "e"]]          []        ["a"]
aux [One "b"; Many [ One "c"; One "d" ]; One "e" ]              []        ["a"]
aux [Many [ One "c"; One "d"]; One "e"]                         []        ["b"; "a"]
aux [One "c"; One "d"]                                          [One "e"] ["b"; "a"]
aux [One "d"]                                                   [One "e"] ["c"; "b"; "a"]
aux [One "e"]                                                   []        ["d"; "c"; "b"; "a"]
aux []                                                          []        ["e"; "d"; "c"; "b"; "a"]
List.rev ["e"; "d"; "c"; "b"; "a"]
["a"; "b"; "c"; "d"; "e"]
``````