Как вставить в середину списка, будучи дружественным к хвосту, но без ущерба для производительности?

Question

Так что у меня есть эта функция, которая, кажется, не является дружественной к хвосту, верно?

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    match bar with
    | [] -> [ foo ]
    | head::tail ->
        if (foo.Compare(head)) then
            foo::bar
        else
            head::(insertFooInProperPosition foo tail)

Затем я пытаюсь выяснить, как использовать аккумулятор, чтобы последнее, что делает функция, это сам вызов, и я придумываю следующее:

let rec insertFooInProperPositionTailRec (foo: Foo) (headListAcc: list<Foo>) (bar: list<Foo>): list<Foo> =
    match bar with
    | [] -> List.concat [headListAcc;[ foo ]]
    | head::tail ->
        if (foo.Compare(head)) then
            List.concat [headListAcc; foo::bar]
        else
            insertFooInProperPosition foo (List.concat [headListAcc;[head]]) tail

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    insertFooInProperPositionTailRec foo [] bar

Однако, насколько я понимаю, использование List.concat сделает эту функцию намного менее эффективной, верно? Итак, как мне поступить и сделать это преобразование правильно?

Answer 1

@ Решение AlexAtNet выглядит не плохо, но если вы все еще хотите рекурсивную работу, вы можете избежать такого concat называет это так:

let rec insertFooInProperPositionTailRec (foo: Foo)
                                         (headListAcc: list<Foo>)
                                         (bar: list<Foo>)
                                         : list<Foo> =
    match bar with
    | [] -> List.rev (foo::headListAcc)
    | head::tail ->
        if (foo.Compare(head)) then
            let newAcc = List.rev headListAcc
            [ yield! newAcc
              yield! foo::bar ]
        else
            let newAcc = head::headListAcc
            insertFooInProperPositionTailRec foo newAcc tail

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    insertFooInProperPositionTailRec foo [] bar

Не уверен, что он более производительный, чем @AlexAtNet, ммм...

Answer 2

К сожалению, вы не можете создать список F# от головы до хвоста (если вы не используете функции, встроенные в библиотеку F# Core, которые используют мутацию под капотом). Поэтому, вероятно, лучшая идея состоит в том, чтобы создать новый список из старого, предварительно добавив следующие элементы и вставив foo в правильном месте. В конце новый список переворачивается, чтобы получить тот же порядок, что и старый список:

let insertFoo (foo : Foo) bar =
    let rec loop acc = function
        | [] -> prep (foo :: acc) []
        | x :: xs ->
            if foo.Compare x
            then prep (x :: foo :: acc) xs
            else loop (x :: acc) xs
    and prep acc = function
        | [] -> acc
        | x :: xs -> prep (x :: acc) xs
    loop [] bar |> List.rev

Я думаю, что @knocte был быстрее с эквивалентным решением...

Answer 3

Ваше решение выглядит нормально, если требуется использование рекурсии. Однако эта задача может быть выполнена без рекурсии (и немного быстрее).

Чтобы объединить два списка, первый список должен быть скопирован, а его последний элемент должен указывать на первый элемент второго списка. Это O(N), где N - размер первого списка. Растущий список в хвосте требует нескольких конкатенаций, в результате чего получается список обхода для каждого N, что делает сложность квадратичной (надеюсь, я прямо здесь).

Вместо рекурсивного подхода, который добавляет элементы в список, более быстрый подход, вероятно, заключался бы в том, чтобы найти индекс вставки и затем скопировать все элементы перед ним за один раз, а затем объединить его с новым элементом и остальной частью списка. Для этого требуется всего три прохода по списку, поэтому O(N).

let insertFooInProperPosition (foo : Foo) (bar : Foo list) : Foo list =
    bar
    |> List.tryFindIndex (fun v -> v.Compare foo)
    |> function | None -> List.append bar [ foo ]
                | Some i -> let before, after = List.splitAt i bar
                            List.concat [ before; [ foo ]; after ]