создания списка пути в F #

Question

(Это, вероятно, классический, но мне интересно, как лучше всего это выразить)

я начинаю на левой стороне, в какой-то момент. Для некоторых активов я могу вычислить доходность от начальной даты до некоторой будущей даты. С этой будущей даты я могу двигаться дальше во времени рекурсивно.

Я хотел бы сгенерировать весь путь, который идет как можно дальше вправо, но это останавливается до какой-либо намеченной даты.

Вот мой код. «a - актив, и (DateTime * DateTime) - 2 раза, для которых у меня есть цитата для упомянутого базового.

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 

Поскольку я использую yield !, я собираю новый путь для каждого отказа в конце. Итак, я должен удалить дубликат моей последовательности в конце. Мой вопрос: есть ли лучший способ найти полный путь, без устранения дублирования?

Я могу сделать второй проход или добавить аргумент 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 }