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

@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 に答える