Error in code to flatten a list in Ocaml

Question

Hello All I am trying to flatten a list in Ocaml. I am a newbie so please pardon me if my mistake is dumb

So for example, if input is [[1];[2;3];[4]] I should end up with [1;2;3;4].

The idea I am trying to use is as follows Iterate through the list from the right (Using fold_right) with accumaltor = [] The pseudo code is as follows

func flatten(list,  accumalator) 
  For each item from right to left in list 
     If Item is a scalar then n :: accumalator
     Else fi Item is a list of form head :: tail then
               head :: flatten (tail, accumalator).

I think that theoretically the algorithm is correct, but please let me know if you disagree.

Now to my OCaml code to implement this algorithm

let rec flatten acc x =
    match x with 
           n -> n :: acc
        | [x] -> x :: acc
        | head :: remainder -> 
            head :: ( my_flat acc remainder ) 
 and my_flat = List.fold_right flatten
 ;;

 my_flat [] [[1];[2;3];[4]]

The Error I get is the following Error: This expression has type 'a but an expression was expected of type 'a list

The error occurs on the line that reads head :: ( my_flat acc remainder ) in the last pattern in the match statement

Any help is appreciated.

Answer 1

In OCaml, all the elements of a list must be the same type. Thus the value [1; [2; 3]; 4] is invalid all by itself. It contains two elements that are of type int and one element of type int list. In essence, your statement of the problem to be solved is impossible.

$ ocaml312
        Objective Caml version 3.12.0

# [1; [2; 3]; 4];;
Characters 4-10:
  [1; [2; 3]; 4];;
      ^^^^^^
Error: This expression has type 'a list
       but an expression was expected of type int

This sounds like a homework problem, so I'll just say that restricting yourself to lists that are valid in OCaml may make it easier to solve.

Edit

OK, the problem can now be solved!

The essence of the reported type error is something like this. You have your accumulated result acc (of type int list in the example). You want to add the list x (also of type int list) to it. You've broken x into head (an int) and remainder (an int list). As you can see, remainder is not a suitable argument for your my_flat function. It wants an int list list, i.e., a list of lists of ints. In fact, your recursive call should almost certainly go to flatten and not to my_flat.

Another problem I see: the arguments of List.fold_right are: a function, a list, and a starting value. In your test call to my_flat, you're supplying the last two in the other order. The empty list [] is your starting value.

I hope this is enough to get you going. Since you're just starting out with OCaml there will probably be another problem or two before it works.

Edit 2

Here are a couple more comments, which might be spoilers if you're still working on your own solution....

A tidier version of your function my_flat is in the OCaml standard library under the name List.flatten. It's interesting to look at the implementation:

let rec flatten = function
    [] -> []
  | l::r -> l @ flatten r

I'd call this a very elegant solution, but unfortunately it's not tail recursive. So it will consume some (linear) amount of stack space, and might even crash for a very long list.

Here's one based on the same idea, using the standard FP accumulator trick to get tail recursive behavior (as noted by Thomas):

let flatten2 ll =
    let rec go acc = function
    | [] -> List.rev acc
    | l :: r -> go (List.rev_append l acc) r
in
    go [] ll

As is often the case, the tail recursive version accumulates the result in reverse order, and reverses it at the end.

Answer 2

You can start by writing directly your algorithm, by decomposing the base cases of your input value, ie. the input list is either empty, or the head of the input list is empty, or the head of the input list has a head and a tail:

let rec flatten = function
  | []          -> []
  | []     :: t -> flatten t
  | (x::y) :: t -> x :: (flatten (y::t))

You can then optimize the function, because this code is not tail-recursive and thus will crash when lists become too big. So you can rewrite this by using the usual technique:

let flatten list =
  let rec aux accu = function
    | []          -> accu
    | []     :: t -> aux accu t
    | (x::y) :: t -> aux (x::accu) (y::t) in
  List.rev (aux [] list)

So my advice is: start by decomposing your problem based on the input types, and then later use accumulators to optimize your code.

Answer 3

I like this one, where the auxiliary function takes the accumulator, the first element of the list of lists, and the rest of the list of lists, it is clearer for me :

let flatten list =
  let rec aux acc list1 list2 =
    match list1 with
      | x :: tail -> aux (x :: acc) tail list2
      | [] ->
        match list2 with
          | [] -> List.rev acc
          | x :: tail -> aux acc x tail
  in
  aux [] [] list

Answer 4

Thanks for all your help Here is the code I used to solve this problem

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
        |  head :: remainder -> head :: ( flatten_each acc remainder )
in
List.fold_right flatten_each ( List.rev list ) []
;;

Edit: as pointed out by Thomas this solution is not tail recursive. Tail recursive version is below

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
            |  head :: remainder -> (flatten_each (acc @ [head]) remainder )
    in
     List.fold_right flatten_each list []
;;