使用返回元组的函数进行尾部调用优化

Question

我有一个简单的函数，在索引处拆分列表:

let rec split_at ls i =
match i with
| 0 -> ([], ls)
| _ ->
match ls with
| [] -> raise Not_found
| h::t ->
match split_at t (i - 1) with
| (left, right) -> ((h :: left), right)

是否有办法让OCaml编译器优化这个函数使用恒定的堆栈空间?

我试过使用@tail_mod_cons，但它不起作用。我明白调用并不是真的在尾部位置，但感觉应该是可优化的。

Answer 1

如果我们将新前缀的构造与使用引用返回后缀的函数部分分开，则可以用部分tail_mod_cons的方式编写函数split_at:

let[@tail_mod_cons] rec split_at r ls i =
match i with
| 0 -> r := ls; []
| _ ->
match ls with
| [] -> raise Not_found
| h::t ->
h:: (split_at[@tailcall]) r t (i - 1)
let split_at ls i =
let r = ref [] in
let l = split_at r ls i in
l, !r

Answer 2

首先，让我们通过在i和ls的元组上进行模式匹配并使用本地let绑定而不是最后的匹配表达式来清理函数。

let rec split_at ls i =
match i, ls with
| 0, _    -> ([], ls)
| _, []   -> raise Not_found 
| _, h::t -> 
let (left, right) = split_at t (i - 1) in
(h::left, right)

正如Jeffrey所说，cons (::)不在尾部调用位置，因此tail_mod_cons对您没有任何作用。如果我们尝试使用它，我们会得到一个警告:

Lines 1-7, characters 33-20:
Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons
but is never applied in TMC position.

正如所暗示的那样，让你的大脑使用累加器修改尾部递归是微不足道的。

let split_at lst n =
let rec aux lst n first_part =
match n, lst with  
| 0, _    -> (List.rev first_part, lst)
| _, []   -> raise Not_found
| _, h::t -> aux t (n - 1) (h::first_part)
in
aux lst n []

Answer 3

我的理解是，"尾模";通过传递一个不完整的构造函数来工作，被调用的函数应该将其答案放入该构造函数中。因此，为了使优化工作，你必须能够将你的问题转化为一个解决方案。

如果你把这个问题分成两部分也许会奏效。第一部分复制列表的前n个元素。第二部分返回列表中除前n个元素外的所有元素。

第二部分很简单，可以递归地实现tail。似乎你应该能够使用"tail mod conquot;来复制一个列表。