OCaml中函数combinations的尾递归版本

Question

OCaml中函数combinations的尾递归版本

5

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

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？

- Jackson Tale

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phimuemue · 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的递归调用之后调用某些东西。

- lukstafi · Answer 2

通常我们使用继续传递风格（continuations-passing-style），就像phimuemue的回答中所示。例如：

let rec prefix_cps tree k =
  match tree with
  | Tip -> k []
  | Node (left,n,right) ->
    prefix_cps left (fun nleft ->
        prefix_cps right (fun nright ->
            k (n :: nleft @ nright)))
let prefix_cps t = prefix_cps t (fun l -> l)

然而，有时我们可以即兴重新排列输入：

let rec prefix_tr t =
  let rec loop queue = function
    | Tip -> queue
    | Node (l, n, Tip) -> loop (n::queue) l
    | Node (l, k, Node (rl, n, rr)) ->
      loop queue (Node (Node (l, k, rl), n, rr)) in
  loop [] t