OCaml 函数需要说明

Question

我正在尝试编写一个 OCaml 函数，它采用 list 中的 list 和 return 中最长的列表，我不断得到 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。如果我们只为单个元素添加 case，就可以解决这个问题。

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

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

但是你的功能不是tail-recursive。将它与足够大的列表一起使用，你会得到堆栈溢出。我们可以通过使用带有累加器参数的局部作用域辅助 (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

扩展 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

OCaml 函数需要说明

OCaml function need clarification

ocaml