F # продолжение идет на StackOverflowException

Question

Привет, ребята. Я реализую функцию F #, которая принимает два списка типа: (int * float) list.Эти два списка имеют разные длины.Элемент int пары представляет собой увеличивающийся код.Я хотел создать новый список, который будет содержать пару (int * float) для каждых двух элементов двух списков, имеющих одинаковый код.Важно отметить, что коды в списках расположены в порядке возрастания.Эти списки, вероятно, немного длинны, например, 2-3000 элементов. Поэтому я попытался реализовать эту функцию, используя стиль передачи продолжения, чтобы избежать исключений StackOverflowException.но, к сожалению, я потерпел неудачу.

Это функция, я надеюсь, вы дадите мне какие-нибудь советы!

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

Здесь вы вызываете продолжение, но этот вызов не является хвостовым, потому что вам все еще нужно использовать минусы (code, Math.Abs ​​(rate-rate2)) для результата (k 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) List.rev

EDIT: после второго взгляда я думаю, что 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