This expression has type 'a list option but an expression was expected of type 'b list

Question

I am writing a function in ocaml that returns the longest list in a list using the type option and using List.fold_right

let longest( lst : 'a list list) : 'a list option = 
  List.fold_right( fun (i : 'a list)  (y : 'a list option) -> if List.length i > List.length y then (Some i) y else y) lst None 

However i keep getting this error

This expression has type 'a list option
but an expression was expected of type 'b list

The function should return Some followed by the longest list or none if it is empty

Answer 1

Handling [] as special case, dropping the unused x argument and reducing the number of times List.length is called to once per list I get this:

let longest lst =
  match lst with   
   | [] -> None   
   | x :: xs -> 
      Some (fst (List.fold_right
        (fun i ((y, ly) as p) ->
          let li = List.length i
          in
            if li > ly
            then (i, li)
            else p)
        xs
        (x, List.length x)));;

val longest : 'a list list -> 'a list option = <fun>
# longest [];;
- : 'a list option = None
# longest [[1]; [1;2;3]; [1;2]];;
- : int list option = Some [1; 2; 3]

Answer 2

Let's make this a bit easier to digest.

let longest (lst : 'a list list) (x : 'a list option) = 
  List.fold_right 
    (fun (i : 'a list)  (y : 'a list option) -> 
       if List.length i > List.length y then (Some i) y 
       else y) 
    lst 
    None 

The specific issue this is complaining about is related to:

List.length y

In this situation y is supposed to be of type 'a list option but List.length expects a value of type 'a list.

You need to do some pattern-matching in the function you pass to List.fold_right to determine if the init value (in your code confusingly represented as y) is None or Some ... and then handle it accordingly.

It might look something like the following. Please note that the type annotations you've used are extraneous as OCaml will infer the types.

let longest lst =
  List.(
    let f x i =
      match i with 
      | None                                  -> ...
      | Some lst' when length x > length lst' -> ...
      | _                                     -> ...
    in
    fold_right f lst None
  )