OCaml中的尾递归合并排序 [英] Tail-recursive merge sort in OCaml

问题描述

我正在尝试在OCaml中实现尾递归列表排序功能，并且给出了以下代码:

I’m trying to implement a tail-recursive list-sorting function in OCaml, and I’ve come up with the following code:

let tailrec_merge_sort l =
  let split l = 
    let rec _split source left right =
      match source with
        | [] -> (left, right)
        | head :: tail -> _split tail right (head :: left) 
    in _split l [] []
  in

  let merge l1 l2 = 
    let rec _merge l1 l2 result =
      match l1, l2 with
        | [], [] -> result
        | [], h :: t | h :: t, [] -> _merge [] t (h :: result)
        | h1 :: t1, h2 :: t2 ->
            if h1 < h2 then _merge t1 l2 (h1 :: result)
            else            _merge l1 t2 (h2 :: result)
    in List.rev (_merge l1 l2 [])
  in

  let rec sort = function
    | [] -> []
    | [a] -> [a]
    | list -> let left, right = split list in merge (sort left) (sort right)
  in sort l
;;

但是，它似乎实际上不是尾递归的，因为我遇到了评估期间堆栈溢出(循环递归?)"错误.

Yet it seems that it is not actually tail-recursive, since I encounter a "Stack overflow during evaluation (looping recursion?)" error.

能否请您帮我找出这段代码中的非尾递归调用?我已经搜索了很多，却没有找到它.难道是sort函数中的let绑定?

Could you please help me spot the non tail-recursive call in this code? I've searched quite a lot, without finding it. Cout it be the let binding in the sort function?

推荐答案

表达式

merge (sort left) (sort right)

不是尾递归的；它会递归地调用(左排序)和(右排序)，而调用中还有剩余工作(合并).

is not tail-recursive; it calls both (sort left) and (sort right) recursively while there is remaining work in the call (merge).

我认为您可以使用额外的延续参数对其进行修复:

I think you can fix it with an extra continuation parameter:

  let rec sort l k =
    match l with
    | [] -> k [] 
    | [a] -> k [a] 
    | list -> let left, right = split list in sort left (fun leftR -> sort right (fun rightR -> k (merge leftR rightR)))
  in sort l (fun x -> x)

这篇关于OCaml中的尾递归合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！