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)

List.fold_left

函数概括了这种“使用累加器迭代列表”行为。

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)

fold_left

函数的非常基本的实现可能具有启发性。

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

Answer 2

为了扩展克里斯的答案..您可能会在现实生活中使用列表模块的功能。

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