創建路徑的F＃

Question

（這可能是一個經典的，但我不知道如何以最佳方式表達出來）

列表我開始在左邊，在某個日期。 對於一些資產，我可以計算從開始日期到某個未來日期的回報。 從未來的日子，我可以遞歸地進一步在時間上進一步。

我想生成儘可能正確的所有路徑，但在某個目標日期之前停止。

這是我的代碼。 'a是一項資產，並且（DateTime * DateTime）是我爲此基礎報價的兩倍。

member this.getPaths dtstart dtend : Set<('a*(DateTime*DateTime)) list>= 
    let rec getPaths dtstart dtend (pastpath:List<'a*(DateTime*DateTime)>) : seq<('a*(DateTime*DateTime)) list>= 
     let udls = this.getUnderlyingsQuotingAt dtstart 
     let onestep = seq { for udl in udls do 
           let qt = this.QuoteNextAfterSrict udl dtstart 
           if qt.IsNone || (qt.Value |> fst > dtend) then 
            yield pastpath |> List.rev 
           else 
            let nextdate = qt.Value |> fst 
            yield! (getPaths nextdate dtend ((udl, (dtstart, nextdate))::pastpath)) } 
     onestep 
    getPaths dtstart dtend List.empty |> Set.ofSeq 

由於我使用屈服！我會收集到底每次失敗了一條新路。 所以，我最終必須去除我的序列。 我的問題是：有沒有更好的方法來找到完整的路徑，而沒有重複刪除？

我可以做第二遍或者添加一個List參數，但是有一些「純」的方法可以一次完成這個嗎？

更新

我想我得到了整個做法不妥許多無用的內部循環。 可能矢量化下一個可用的引號會很有用。我將在重構後更新代碼。

更新2

第一重寫是移動產生以下|> List.rev一個水平之上，從而允許切割不必要的探索。

member this.getPaths dtstart dtend : Set<('a*(DateTime*DateTime)) list>= 
    let count = ref 0 

    printfn "computing path from %A to %A " dtstart dtend 
    let rec getPaths dtstart dtend (pastpath:List<'a*(DateTime*DateTime)>) : seq<('a*(DateTime*DateTime)) list>= 
     let udls  = this.getUnderlyingsQuotingAt dtstart 
     let udlquotes = udls |> Seq.map (fun udl -> (udl , this.QuoteNextAfterSrict udl dtstart)) 
               |> Seq.filter (fun (_, q) -> q.IsSome) 
               |> Seq.map (fun (udl, q) -> (udl, q.Value)) 
               |> Seq.filter (fun (_, q) -> fst q <= dtend ) 

     let onestep = seq { if udlquotes.IsEmpty then 
           yield pastpath |> List.rev 
          else 
           for (udl, q) in udlquotes do 
             let nextdate = (fst q) 
             count := !count + 1 
             if !count%1000 = 0 then printfn "!count %A , path : %A " !count pastpath 
             yield! (getPaths nextdate dtend ((udl, (dtstart, nextdate))::pastpath) ) 
         } 
     onestep 
    getPaths dtstart dtend List.empty |> Set.ofSeq 

Answer 1

我不太瞭解你的算法，但我認爲一般結構看起來不錯。 「重複數據刪除」是什麼意思？如果您指的是在遞歸處理結束時使用的List.rev調用，那麼這是相當常見的模式（並且我不認爲有更好的方法來做到這一點）。

關於F＃編碼風格，在分析qt值時（因爲無法使用內置模式編碼條件），您無法輕鬆使用模式匹配，這有點讓人失望。但是，您可以定義當輸入比參數大相匹配的輔助參數活躍模式：

let inline (|MoreThan|_|) limit input = 
    if input > limit then Some input else None 

使用模式，可以讓你seq的身體有點更具可讀性：

let rec getPaths dtstart dtend pastpath = seq { 
    let udls = this.getUnderlyingsQuotingAt dtstart 
    for udl in udls do 
    match this.QuoteNextAfterSrict udl dtstart with 
    | None 
    | Some (MoreThan dtend _, _) -> 
     yield pastpath |> List.rev 
    | Some (nextdate, _) -> 
     let newpath = (udl, (dtstart, nextdate))::pastpath 
     yield! getPaths nextdate dtend newpath }