为什么不能将这两个列表传递到OCaml的递归函数中？

Question

我试图在OCaml中编写一个更简单的解析器，但是遇到了我无法解决的问题。我已经将代码简化为最少的示例，这给了我同样的错误：

我想在OCaml中编写一个函数，该函数接受一个整数列表并输出一个字符串列表。规则是：如果1连续有两个s，则输出"eleven"；如果仅1输出一个，则输出"one" 其他任何数字"other"。此python代码可以完成此工作：

def convert(numbers, names):
    if len(numbers) == 0:
      return names
    n = numbers.pop(0)
    if n == 1:
        if len(numbers) > 0 and numbers[0] == 1:
            numbers.pop(0)
            names.append("eleven")
        else:
            names.append("one")
    else:
        names.append("other")
    return convert(numbers, names)

convert([1, 1, 2, 1, 3, 1], [])
# -> ['eleven', 'other', 'one', 'other', 'one']

我在OCaml中的尝试是这样的：

let rec convert (numbers : int list) (names : string list) = function
  | [] -> List.rev names
  | 1 :: 1 :: t -> convert t ("eleven" :: names)
  | 1 :: t -> convert t ("one" :: names)
  | _ :: t -> convert t ("other" :: names)
;;

convert [1; 1; 2; 3] [];;

我认为将会发生的事情将是convert递归地调用自身：整数列表将变小，字符串列表将变大，直到不再有整数为止：

convert [1; 1; 2; 1; 3; 1] []
-> convert [2; 1; 3; 1] ["eleven"]
  -> convert [1; 3; 1] ["other"; "eleven"]
    -> convert [3; 1] ["one"; "other"; "eleven"]
      -> convert [1] ["other"; "one"; "other"; "eleven"]
        -> convert [] ["one"; "other"; "one"; "other"; "eleven"]
          -> ["eleven"; "other"; "one"; "other"; "one"]

但是实际发生的是编译错误：

Error: This expression has type int list -> string list
       but an expression was expected of type string list

突出显示文字 convert t ("eleven" :: names)

这里发生了什么？我不明白为什么这行不通。

Answer 1

function | ...实际上是的简写fun x -> match x with | ...。那是：

let convert numbers names = function
  | ...

相当于

let convert numbers names something_else =
  match something_else with
  | ...

convert因此，您的函数需要三个参数，并convert t ("eleven" :: names)返回一个函数，int list -> string list而不仅仅是string list从第一个分支推断出的a 。

替换function为match numbers with进行编译：

let rec convert (numbers : int list) (names : string list) =
  match numbers with
  | [] -> List.rev names
  | 1 :: 1 :: t -> convert t ("eleven" :: names)
  | 1 :: t -> convert t ("one" :: names)
  | _ :: t -> convert t ("other" :: names)
;;

convert [1; 1; 2; 3] [];;