1

所以我有这个似乎是非尾调用友好的功能，对吧？

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 的使用会使该功能的效率大大降低，对吗？那么我该如何正确地进行这种转换呢？

4

3 回答 3

1

如果需要使用递归，您的解决方案看起来不错。然而，这个任务可以在没有递归的情况下完成（而且速度更快一些）。

要连接两个列表，应复制第一个列表，其最后一个元素应指向第二个列表的第一个元素。这是 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 ]
于 2018-01-17T12:03:01.880 回答
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 的性能更高，嗯...

于 2018-01-17T12:50:05.753 回答
1

不幸的是，您无法从头到尾构建 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 使用等效的解决方案会更快……</p>

于 2018-01-17T13:09:01.720 回答