不带递归的长度函数ocaml

Question

我正在尝试重写

List.length

函数而不使用递归。这是我的代码：

(* given *)
type 'a list =
  | []
  | (::) of 'a * 'a list
let nil : 'a list = []
let cons (hd : 'a) (tl : 'a list): 'a list = hd :: tl

let length (ls : 'a list): int =
  let i = fold_left(fun x y -> Fun.const 1 :: y) [] ls in
  fold_left(fun x y -> x + y) 0 i

OCaml 在最后一行

fold_left(fun x y -> x + y) 0 i

给了我一个错误，并说我的

i

这里有

type ('a -> int) list

但需要一个表达式

type int list

，有什么办法可以解决这个问题吗？谢谢！

Answer 1

我并不完全清楚你想用

Fun.const

实现什么，但你实际上可以用一个

length

实现

fold_left

：

let length l =
  fold_left (fun acc _ -> acc+1) 0 l

Answer 2

您的尝试存在一些问题。

由于

Fun.const

在这种情况下创建了一个始终返回

1

的函数，并且您的表达式解析为：

(Fun.const 1) :: y

您第一次使用

List.fold_left

正在生成一个全部返回一个的函数列表。但有没有价值

1

。

因此，当您使用

fold_left (fun x y -> x + y) 0 i

时，您正在尝试向 int 添加一个函数。显然这是行不通的。您需要应用该函数的一些参数。

let length (ls : 'a list): int =
  let i = List.fold_left(fun x y -> Fun.const 1 :: y) [] ls in
  List.fold_left(fun x y -> x + y ()) 0 i

这可以编译。 但是... 类型看起来不太正确。

val length : (unit -> int) list list -> int = <fun>

这是由于函数

List.fold_left

的参数顺序错误造成的。第一个参数是初始值。第二个是列表中的第一个元素。

如果我们改变这一点：

let length (ls : 'a list): int =
  let i = List.fold_left (fun y _ -> Fun.const 1 :: y) [] ls in
  List.fold_left (fun x y -> x + y ()) 0 i

这个函数的类型是：

val length : 'a list -> int = <fun>

但正如 Blackbeans 所指出的那样，有一种更简单的方法可以通过一次调用

List.fold_left

来编写此代码。