how to insert in the middle of a list, being tail-call friendly but without hurting performance?

Question

So I have this function which seems to be non-tail-call friendly, right?

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)

Then I try to figure out how to use an accumulator so that the last thing done by the function is call itself, and I come up with this:

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

However, as far as I understand, the usage of List.concat would make this function much less efficient, right? So then how would I go and do this conversion properly?

Answer 1

Your solution looks ok if using recursion is required. However, the this task can be achieved without recursion (and a bit faster).

To concatenate two lists the first list should be copied and its last element should point to the first element of the second list. This is O(N) where N is the size of the first list. Growing list at the tail requires multiple concatenations, resulting traversing list for each N, which makes the complexity quadratic (hope I right here).

Instead of recursive approach that adds items to the list, the faster approach would be probably to find the insertion index and then copy all the items before it in one go and then concat it with new item and the rest of the list. This requires only three passes through the list so 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 ]

Answer 2

@AlexAtNet's solution doesn't look bad, but if you still want recursive, you can avoid so much concat calls this way:

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

Not sure if it's more performant than @AlexAtNet's, mmm...

Answer 3

Unfortunately you cannot build up an F# list from head to tail (unless you use functions internal to the F# Core library that use mutation under the hood). Therefore the best idea is probably to build up a new list from the old one, prepending the next elements as we go, and inserting foo at the right point. At the end, the new list is reversed to obtain the same order as the old list:

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

I guess @knocte was quicker with an equivalent solution…