F＃延續繼續StackOverflowException

嗨，大家好我正在實現一個F＃函數，它需要兩個類型列表：（int * float）list。這兩個名單有不同的lentgths。這對夫婦的int元素是一個漸增的代碼。我想要做的是創建一個新列表，其中包含兩個具有相同代碼的列表中的每兩個元素的一對（int * float）。重要的是要注意列表中的代碼正在增加。這些列表可能有點長，比如2-3000個元素，所以我嘗試使用continuation傳遞樣式來實現此函數，以避免StackOverflowExceptions。但可惜我失敗了。F＃延續繼續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

我做錯了什麼？

來源

2011-08-19 Fr.Usai

(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

這也將修復您的結果以相反的順序返回。

來源

2011-08-19 16:54:41 Daniel

實際上，與以前一樣，我得到了StackOverflowException。這有點奇怪，因爲我以相同的方式實現了它，對於稍微不同的任務（採用兩個有序整數列表生成對應列表的函數），並且它沒有問題地進行尾遞歸 –

我剛剛測試了兩個100列表並且沒有發生堆棧溢出。我將列表增加到10億，並且內存不足，但仍然沒有堆棧溢出。 – Daniel

我真的不知道丹尼爾，我已經完成了複製和粘貼，而且我仍然遇到堆棧溢出問題。 –

問題就出在這行

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

在這裏你調用延續，但這個電話是不是因爲尾巴，你仍然需要利弊（代碼，Math.Abs（速率率2））到的結果（ 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 []

來源

2011-08-19 16:24:00 desco

使用蓄能器將輸出結果以相反的順序，這對他目前的實施也做（我以爲是不是故意的）。 – Daniel

謝謝，解決！ –

對於替代的答案，看看這樣：http://fssnip.net/75

該函數採用幾個序列並返回其中根據一些匹配函數匹配對。我沒有批量測試它。

功能在更大的片段在這裏實際上是用：http://fssnip.net/76

來源

2011-08-20 13:23:57 Kit

F＃延續繼續StackOverflowException

回答

相關問題