Tail-recursive version of functional combinations in OCaml

Question

A function without tail recursive combinations can be written as follows:

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)))

Note that I use List.rev_appendat least for the appendtail recursive version

This means generating all combinations if you want to get k elements from the list.

I'm just wondering if it's possible to create a full recursive version combinations?

Answer 1

You can use the continue 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 , " ", " ".

Answer 2

- , 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