创建路径的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 }