4

次のような最後のアキュムレータ値を返すカスタム展開関数を作成しようとしています:

val unfold' : generator:('State -> ('T * 'State) option) -> state:'State -> 'T list * 'State

私は次のようにすることができました：

let unfold' generator state =
    let rec loop resultList state =
        match generator state with
        | Some (value, state) -> loop (value :: resultList) state
        | None -> (List.rev resultList), state
    loop [] state

List.revしかし、結果のリストを避けて、正しい順序ですでに生成したかったのです。リストを作成するには継続を使用する必要があると思いますが、私は関数型プログラミングにまったく慣れていないため、まだ継続について理解できていません。私が想像できるすべての選択肢は、結果のリスト内にアキュムレータを置くか、関数によって返されることを許可しません。

これを行う方法はありますか？

これは個人的な学習演習であるため、完成したコードを単に提供するのではなく、その方法を説明する回答を希望します。

4

2 に答える 2

5

a なしで行う方法は、パラメーターList.revの代わりに関数を渡すことです。resultListその関数を と呼びましょうbuildResultList。各ステップで、この関数はリストの既に作成された末尾を取得し、現在のアイテムを先頭に追加し、これを前のステップの関数に渡します。これは前のアイテムを追加し、前のアイテムの関数に渡します。前のステップなど。このチェーンの最後の関数は、最初の項目をリストに追加します。再帰ループ全体の結果は、チェーンの最後の関数 (前のすべての関数を呼び出します) になり、空のリストを引数として呼び出します。残念ながら、これはコードを書くだけでなくてもできる限り明確です。

ただし、問題は、「より良い」の定義については、これ以上良くないということです。計算は「順方向」に進行し、結果のリストは「逆方向」に構築されるため (head :: tail、Lisp スタイル)、結果をどこかに蓄積する必要があります。コードでは、一時的なリストに蓄積していますが、継続を使用するように変更すると、チェーン内で相互に参照する一連のクロージャーとしてヒープに蓄積されます。難読化されているだけで、本質的には同じリストであると主張できます。

あなたが試すことができる別のアプローチは、代わりに遅延シーケンスを使用することです: 再帰seq計算を構築しyield、現在のアイテムとそれyield!自体を構築します。その後、このシーケンスを列挙できます。「一時的な」ストレージは必要ありません。ただし、それでも最後にリストを取得したい場合は、 を介してシーケンスをリストに変換する必要があります。それがList.ofSeqどのように実装されるかを推測してください。理論的には、純粋に数学的な観点からはList.ofSeq、まったく同じ方法で実装されます。つまり、最初に一時リストを作成してから逆にすることです。しかし、F# ライブラリはここでごまかします。変更可能な方法でリストを作成するため、元に戻す必要はありません。

最後に、これは学習課題であるため、遅延シーケンスに相当するものを自分で実装することもできます。現在、標準の .NET シーケンス (エイリアスである別名) は本質的にIEnumerable<_>ミュータブルです。次のアイテムに移動するたびに、イテレータの内部状態を変更しています。あなたはそれを行うことができます、または、学習の精神で、不変の等価物を行うことができます. これはほとんどリスト (head::tail) に似ていますが、lazyであるため、「tail」は実際のシーケンスではなく promise でなければならないという点が異なります。Seq<_>

type LazySeq<'t> = LazySeq of (unit -> LazySeqStep<'t>)
and LazySeqStep<'t> = Empty | Cons of head: 't * tail: LazySeq<'t>

列挙する方法は関数を呼び出すことであり、次の項目とシーケンスの末尾を返します。次に、 unfold を関数として記述して、現在のアイテムを としてhead返し、それ自体をクロージャとしてラップして返すだけtailです。実際、非常に単純であることがわかります。

于 2016-09-23T13:18:09.987 に答える
2

Fyodor Soikin's answer のおかげで、結果の関数は次のとおりです。

let unfold' generator state =
    let rec loop build state =
        match generator state with
        | Some (value, state) -> loop (fun newValue -> build (value :: newValue)) state
        | None -> (build []), state
    loop id state
于 2016-09-23T13:50:34.883 に答える