ocaml - OCaml 中函数组合的尾递归版本

Question

非尾递归组合函数可以这样写:

let rec combinations l k =
  if k <= 0 || k > List.length l then []
  else if k = 1 then List.map (fun x -> [x]) l 
  else 
    let hd, tl = List.hd l, List.tl l in
    combinations tl k |> List.rev_append (List.map (fun x -> hd::x) (combinations tl (k-1)))

请注意，我使用 List.rev_append至少给出了 append尾递归版本

这意味着如果您想从列表中取出 k 个元素，则生成所有组合。

我只是想知道是否有可能创建一个完整的尾递归版本 combinations ?

Answer 1

您可以使用 continuation passing style :

let combos l k =
    let rec aux l k cont =
        if k <= 0 || k > List.length l then cont []
        else if k = 1 then cont (List.map (fun x -> [x]) l)
        else 
            let hd, tl = List.hd l, List.tl l in
            aux tl k 
            (
                fun res1 -> aux tl (k-1)
                (
                    fun res2 -> cont (List.rev_append (List.map (fun x -> hd::x) res2) res1)
                )
            )
    in aux l k (fun x -> x)

这样，您就可以避免在 aux 的递归调用之后调用某些内容。代价是创建一个匿名函数，该函数负责在“原始递归调用”之后进行的“ future 计算”。