此表达式具有类型"a 列表"选项，但表达式应具有"b 列表"类型

Question

我正在OCaml中编写一个函数，该函数使用type选项和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 

然而，我不断地得到以下错误。

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

函数应返回Some，然后是最长列表，如果为空，则返回None。

Answer 1

让我们更容易理解它。

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 

这个抱怨的具体问题与有关

List.length y

在这种情况下，y被假定为类型'a list option，但是List.length期望类型'a list的值。

您需要在传递给List.fold_right的函数中进行一些模式匹配，以确定init值(在代码中混淆地表示为y(是None还是Some ...，然后相应地处理它。

它可能看起来像下面这样。请注意，您使用的类型注释是无关的，因为OCaml将推断类型。

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
)

Answer 2

将[]作为特例处理，删除未使用的x参数，并将List.length的调用次数减少到每个列表一次

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]