F# 延续出现 StackOverflowException

Question

大家好，我正在实现一个 F# 函数，它采用两个类型的列表：(int*float) 列表。这两个列表的长度不同。 这对的int元素是一个递增的代码。 我想做的是创建一个新列表，其中包含两个具有相同代码的列表中每两个元素的 (int*float) 。需要注意的是，列表中的代码是按递增顺序排列的。 这些列表可能有点长，比如 2-3000 个元素，所以我尝试使用连续传递风格来实现这个函数，以避免 StackOverflowExceptions。但遗憾的是我失败了。

这是这个功能，希望大家指点！

let identifiedDifference list1 list2 =
    let rec produceResult (l1, l2) k =
        match l1,l2 with
            | [],[] 
            | _,[]
            | [],_ -> k []
            | (code,rate:float)::xs, (code2,rate2)::ys -> 
                if code = code2 
                    then
                        produceResult (xs, ys) (fun c -> (code,Math.Abs(rate-rate2))::(k c))
                    elif code > code2
                        then produceResult (l1, ys) k
                        else produceResult (xs, l2) k
    produceResult (list1, list2) id

我做错了什么吗？

Answer 1

(fun c -> (code,Math.Abs(rate-rate2))::(k c))

应该是

(fun c ->  k ((code,Math.Abs(rate-rate2))::c))

使其尾递归：

let identifiedDifference list1 list2 =
    let rec produceResult (l1, l2) k =
        match l1,l2 with
            | [],[] 
            | _,[]
            | [],_ -> k []
            | (code,rate:float)::xs, (code2,rate2)::ys -> 
                if code = code2 then produceResult (xs, ys) (fun c ->  k ((code,Math.Abs(rate-rate2))::c))
                elif code > code2 then produceResult (l1, ys) k
                else produceResult (xs, l2) k
    produceResult (list1, list2) id

这也将修复以相反顺序返回的结果。

Answer 2

问题出在这一行

produceResult (xs, ys) (fun c -> (code,Math.Abs(rate-rate2))::(k c))

这里你调用延续，但这个调用不是尾部，因为你仍然需要 cons (code,Math.Abs​​(rate-rate2)) 到 (kc) 的结果

我想你可以从以下构建结果列表由内而外并反转最终结果：

let identifiedDifference list1 list2 =
    let rec produceResult (l1, l2) k =
        match l1,l2 with
            | [],[] 
            | _,[]
            | [],_ -> k []
            | (code,rate:float)::xs, (code2,rate2)::ys -> 
                if code = code2 
                    then
                        produceResult (xs, ys) (fun c -> k((code,Math.Abs(rate-rate2))::c))
                    elif code > code2
                        then produceResult (l1, ys) k
                        else produceResult (xs, l2) k
    produceResult (list1, list2) List.rev

编辑：
经过第二次查看后，我认为这里不需要 CPS，使用累加器应该可以解决问题：

let identifiedDifference list1 list2 = 
    let rec run l1 l2 acc = 
        match l1, l2 with
        | [], _ | _, [] -> List.rev acc
        | (code1, rate1 : float)::xs, (code2, rate2)::ys ->
            if code1 = code2 then
                run xs ys ((code1, abs (rate1 - rate2))::acc)
            elif code1 > code2 then
                run l1 ys acc
            else
                run xs l2 acc
    run list1 list2 []

Answer 3

对于替代答案，请看一下： http://fssnip.net/75

该函数需要几个序列并返回根据某些匹配函数匹配的对。我还没有对其进行过体积测试。

该函数实际上在较大的代码片段中使用： http://fssnip.net/76