3

再帰関数:

let rec listMerge (l1 : 'a list) (l2 : 'a list) =
    if l1.IsEmpty then      l2 
    elif l2.IsEmpty then    l1 
    else                    l1.Head :: l2.Head :: listMerge l1.Tail l2.Tail

さて、私が間違っていない限り、これは実際にはテールコールを実行しません。それ::が正しい連想であると考えていなければ、そのように見えるだけかもしれません。

次に、（読んだものの、今は見つけられなかったものから）エクストラfunなどを使用して、これをテール再帰に簡単に変換できるという印象を受けました。

それで、それは可能ですか？コード？

私の答え:したがって、以下の回答のおかげで、これが関数を変更した方法です:

let listMerge l1 l2 =
    let rec mergeLoop  (l1 : 'a list) (l2 : 'a list) acc =
        if l1.IsEmpty then      (List.rev acc) @ l2 
        elif l2.IsEmpty then    (List.rev acc) @ l1
        else                    mergeLoop l1.Tail l2.Tail (l2.Head :: l1.Head :: acc)
    mergeLoop l1 l2 []
4

5 に答える 5

14

@Ramon が示唆したように、読みやすくするためにパターン マッチングを使用する必要があります。

let rec listMerge xs ys =
    match xs, ys with
    | [], _ -> ys
    | _, [] -> xs
    | x::xs', y::ys' -> x::y::listMerge xs' ys'

ご覧のとおり、2 つの cons コンストラクター(::)が最後の操作でlistMergeあるため、関数は末尾再帰ではありません。

アキュムレータを使用して、末尾再帰的な方法で結果を取得できます。

let listMerge xs ys =
    let rec loop xs ys acc =
        match xs, ys with
        | [], zs | zs, [] -> (List.rev zs)@acc
        | x::xs', y::ys' -> loop xs' ys' (y::x::acc)
    List.rev (loop xs ys [])

上記の関数ではList.rev、いくつかのパターンを追加して 2 つのリストを両方とも空になるまで分解すると、最初の呼び出しを回避できます。

F# には、継続渡しスタイルに沿ったシーケンス式を使用した末尾再帰アプローチがあります。

let listMerge xs ys =
    let rec loop xs ys =
        seq {
            match xs, ys with
            | [], zs | zs, [] -> yield! zs
            | x::xs', y::ys' -> 
                yield x
                yield y
                yield! loop xs' ys'
        }
    loop xs ys |> Seq.toList

このアプローチは便利で、元の処方に近いので気に入っています。

于 2012-10-31T09:15:36.960 に答える
2

構築された結果を後続の呼び出しで蓄積しlistMerge、最終的に蓄積された結果を返すことができます。私の F# スキルはかなり錆びていますが、ここでは単純な Lisp 関数について説明します。

(defun list-merge (xs ys &optional acc)
  (cond ((< 0 (length xs)) (list-merge (rest xs) ys (cons (first xs) acc)))
        ((< 0 (length ys)) (list-merge xs (rest ys) (cons (first ys) acc)))
        (t acc)))

(list-merge '(1 2 3) '(3 4 5)) ;=> (5 4 3 3 2 1)
(list-merge '() '(1 2))        ;=> (2 1)
(list-merge '() '())           ;=> nil
于 2012-10-31T09:00:18.697 に答える
1

アキュムレータを使用した単純なバージョン:

let rec listMerge (l1 : 'a list) (l2 : 'a list) acc =
    if l1.IsEmpty then      (List.rev l2)@acc 
    elif l2.IsEmpty then    (List.rev l1)@acc
    else                    listMerge l1.Tail l2.Tail (l1.Head :: l2.Head :: acc)

これを 200 万個の要素リストでテストしましたが、スタック オーバーフローはなかったので、これは末尾再帰であると確信しています。

于 2012-10-31T09:16:20.740 に答える
0

F＃PowerPackにある元のF＃コードを再利用する必要があると思います。
実際、必要なのは、リストのサイズが異なる場合List.fold2に関数が例外をスローしないことを除いて、代わりに次のように長いリストの残りを処理することです。SR.listsHadDifferentLengths

let l1 = ["A1"; "A2"; "A3"; "A4"; "A5"; "A6"; "A7"]
let l2 = ["B1"; "B2"; "B3"; "B4"]

let expectedResult = ["A1"; "B1"; "A2"; "B2"; "A3"; "B3"; "A4"; "B4"; "A5"; "A6"; "A7"]

これが私たちのやり方です：

[<CompiledName("Fold2Tail")>]
let fold2Tail<'T1,'T2,'State> f g1 g2 (acc:'State) (list1:list<'T1>) (list2:list<'T2>) = 
    let f  = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
    let g1 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g1)
    let g2 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g2)
    let rec loop acc list1 list2 =
        match list1, list2 with 
        | [], [] -> acc
        | _,  []  -> g1.Invoke(acc, list1)
        | [], _   -> g2.Invoke(acc, list2)
        | (h1::t1),(h2::t2) -> loop (f.Invoke(acc,h1,h2)) t1 t2
    loop acc list1 list2

g1およびは、対応するタイプおよび、g2の述語です。両方のリストの残りを処理する方法を説明します。一般的にはタイプが異なるため、2つあることに注意してください。はい、多少オーバーヘッドがありますが、必要に応じて簡単に減らすことができ、普遍性を犠牲にすることができます。'State -> 'T1 list -> 'State'State -> 'T2 list -> 'State'T1'T2

使用法：

let ret =
    fold2Tail
        (fun s x y  -> [ yield! s; yield x; yield y ] ) // f
        List.append // g1
        List.append // g2
        []          // 'State
        l1 l2
于 2012-10-31T12:52:02.507 に答える
0

パターン マッチングを使用する必要があります。

let rec merge xs ys =
  match xs, ys with
  | [], xs | xs, [] -> xs
  | x::xs, y::ys -> x::y::merge xs ys

テール コールを取得するには、アキュムレータを使用できます。

let merge xs ys =
  let rec loop xys xs ys =
    match xs, ys with
    | [], xs | xs, [] -> List.fold (fun xs x -> x::xs) xs xys
    | x::xs, y::ys -> loop (y::x::xys) xs ys
  loop [] xs ys

または継続渡しスタイル:

let merge xs ys =
  let rec loop xs ys k =
    match xs, ys with
    | [], xs | xs, [] -> k xs
    | x::xs, y::ys -> loop xs ys (fun xys -> k(x::y::xys))
  loop xs ys id
于 2012-11-04T13:18:20.487 に答える