OCaml函数需要澄清

Question

我正在尝试编写一个OCaml函数，该函数接受list的list并返回它们的最长列表，我不断得到n.length和l.length是未绑定的记录字段长度

let rec longest (nss: 'a list list) : 'a list =
match nss with
| [] -> raise (Failure "you entered an empty list")
| n::ns -> 
let l = (longest ns) in
if n.length > l.length then n 
else l

Answer 1

如前所述，您不能在OCaml中的列表中使用.length。相反，您可以将它们传递给List.length。

let rec longest (nss: 'a list list) : 'a list =
match nss with
| [] -> raise (Failure "you entered an empty list")
| n::ns -> 
let l = (longest ns) in
if List.length n > List.length l then n 
else l

但如果我们尝试一下：

# longest [[1;2;3]; [4;5]];;
Exception: Failure "you entered an empty list".

发生这种情况是因为递归最终会导致在空列表上调用longest。如果我们只为单个元素添加一个案例，就可以解决这个问题。

如果我们在一个只有一个列表的列表中寻找最长的列表，那么显然这个列表是最长的，所以我们只返回那个列表。

let rec longest (nss: 'a list list) : 'a list =
match nss with
| [] -> raise (Failure "you entered an empty list")
| [n] -> n
| n::ns -> 
let l = (longest ns) in
if List.length n > List.length l then n 
else l

作为引发异常的替代方法，可以使用option类型。

let rec longest (nss: 'a list list) : 'a list option =
match nss with
| [] -> None
| n::ns ->
(match longest ns with   
| None -> Some n
| Some l when List.length l > List.length n -> Some l
| _ -> Some n)

现在：

# longest [[1;2;3]; [4;5]];;
- : int list option = Some [1; 2; 3]
# longest [];;
- : 'a list option = None

但是你的函数不是尾递归的。将它与足够大的列表一起使用，会导致堆栈溢出。我们可以通过使用带有累加器参数的局部作用域辅助(aux(函数来克服这一问题。

let longest lst =
let rec aux lst acc =
match lst with   
| [] -> acc
| fst::rst when List.length fst > List.length acc -> aux rst fst
| _::rst -> aux rst acc 
in
match lst with
| [] -> None
| n::ns -> Some (aux ns n)

CCD_ 10函数将此"；用累加器迭代列表"；行为

let longest lst =
let len = List.length in
let maxlen list1 list2 =
if len list2 > len list1 then list2
else list1
in
match lst with
| [] -> None
| (x::xs) -> Some (List.fold_left maxlen x xs)

CCD_ 11函数的一个非常基本的实现可能是有指导意义的。

let rec fold_left f init lst =
match lst with
| [] -> init
| (x::xs) -> fold_left f (f init x) xs

Answer 2

扩展Chris的答案。。您可能会在现实生活中使用List模块的功能。

let lol =
[
[1];
[1; 2; 3; ];
[1; 2; 3; 4; 5; ];
[1; 2; 3; 4; ];
[1; 2; ];
]
let ans =
List.fold_left
(
fun a e -> 
(*your code goes here*)
)
None
lol