4

関数型プログラミングの純粋関数は、副作用のない関数です。これの意味の1つは、入力パラメーターの値を変更できないことです。これはメモリ使用率の不利と見なすことができますか？
たとえば、リストを取得して別の要素を追加するだけの関数があるとします。C ++では、次のように単純にすることができます。


void addElem(std::vector& vec, int a)
{
    vec.insert(a);
}

この関数は明らかに、渡されたオブジェクトによってすでに使用されているよりも多くのメモリを使用しません。
しかし、Haskellでも同じことがこのようなものになるでしょう。

addElem :: [Int]-> Int-> [Int]
addElem xs a = xs ++ [a]

xsは値を変更していないため、この計算では。したがって、関数がxsの2倍のサイズのメモリを消費することになると言っているのは正しいですか。1つはxs用で、もう1つは戻り値用です。または、どういうわけか怠惰な呼び出しは、最後に1つの要素のみを追加することによって、実際にxsが返されることを確認しますか？
私はモナドが副作用をもたらす可能性のある何かを持つ方法であることを知っています。しかし、Monadを使用して、入力を変更し、その値を返すことはできますか？
また、xs ++ [a]をa：xsに変更すると、消費するメモリが少なくなりますか？

4

6 に答える 6

10

純度は、関数が破壊的な更新を行うことができないことを意味します。

xs ++ [a]

完全に評価されている場合は、コピーを作成するxs必要があります。これは、が遅延生成され、他の場所で参照されていない場合、一定のスペースで発生する可能性がxsあります。そのため、作成時にガベージコレクションを行うことができます。または、他にコピーが必要な場合もありますxsが、純度によって両方のリストのセルが同じデータを指すことができるため、データをコピーする必要はなく、スパインのみをコピーする必要があります（最終的な短所によって修正されます）。ただし、コピーが作成された場合でも、古い値xsは引き続き使用できます。

また、xs ++ [a]をa：xsに変更すると、消費するメモリが少なくなりますか？

はい、簡単に再利用できxsます。必要なのは、新しいリストセルを作成し、そのテールポインタがを指すようにすることだけxsです。

コメントから：

C++関数を純粋にしたくありません。入力状態を変えて欲しい。そして、それが私が質問の要点になりたかったことです。

その場合、不純な機能/アクションが必要です。これは、一部のデータ構造で実装することは可能ですが、リストの場合、セルを新たにコピー/構築する必要があります。ただし、要素をに追加するには、std::vector<T>再割り当ても必要になる場合があります。

于 2012-12-20T15:00:51.090 に答える
8

はい、純粋FPは命令型プログラミングよりもメモリを大量に消費する可能性がありますが、プログラムの記述方法やコンパイラの賢さにもよります。特にHaskellコンパイラは非常に強力なオプティマイザを備えており、純粋なFPコードを割り当てられたメモリを再利用する非常に効率的なマシンコードに変換できる可能性があります。ただし、最も賢いコンパイラでさえ、表面的に類似したFP構造を持つ命令型プログラムをシミュレートするプログラムを処理するための最適化が含まれていないため、適切なFPコードを記述する必要があります。

念のために言っておきますが、C++の例は無効です。あなたが意味するなら

v[0] = a;  // assuming v.size() > 0

その後、それは割り当てを行いません。あなたが意味するなら

v.append(a);

次に、の容量に応じて、割り当てる場合と割り当てない場合がありvます。

または、どういうわけか怠惰な呼び出しは、最後に1つの要素のみを追加することによって、実際にxsが返されることを確認しますか？

実装とそのコンテキストでの式の使用に依存します。がxs ++ [a]完全に評価されると、リスト全体がコピーされますxs。部分的に評価される場合、noneと。の間で任意の数の割り当てを行う可能性がありますlen(xs)。

また、xs ++ [a]をa：xsに変更すると、消費するメモリが少なくなりますか？

はい、これにより、O（n）ワーストケースからO（1）ワーストケースの割り当て/追加のメモリ使用に変更されます。時間の複雑さについても同じことが言えます。Haskellでリストを処理するときは、末尾に追加しないでください。それが必要な場合は、差分リストを使用してください。

于 2012-12-20T14:59:36.673 に答える
4

2つの例の関連する違いは、それ自体が純粋か不純かという問題ではなく、データ構造の選択だと思います。

両方のアプローチで単一にリンクされたリストを持つことができ、両方で一定時間更新される配列を持つことができます。純粋なケースでは、データ構造を更新すると意味的にコピーが作成される場合がありますが、それは必ずしも物理的にコピーを作成することを意味するわけではありません。

たとえば、ロープは不変の配列の変形であり、一定時間の連結を可能にします。また、実際にアクセスしている場合にのみ物理コピーを実行するコピーオンライトスキームを内部的に使用することにより、一定時間の機能更新（a.set（i、x）が意味的にコピーを返す）で不変の配列抽象化を行うことができます。新しいバージョンを作成した後の古いバージョン（つまり、不純な場合には利用できない純粋なデータ構造の永続化機能を利用する場合）。

于 2012-12-20T15:45:14.430 に答える
3

ab・strac・tion [ab-strak-shuh n]

具体的な現実、特定のオブジェクト、または実際のインスタンスとは別に、何かを一般的な品質または特性と見なす行為。

トレード・オフ

すべてを同時に達成することはできない要因のバランス

漏れのある抽象化

すべての重要な抽象化は、ある程度、リークがあります。

関数型プログラミングは抽象化と見なすことができ、すべての抽象化がリークするため、いくつかのトレードオフを行う必要があります。

于 2012-12-20T15:01:03.767 に答える
3

xsは値を変更していないため、この計算では。したがって、関数がxsの2倍のサイズのメモリを消費することになると言っているのは正しいですか。1つはxs用で、もう1つは戻り値用です。

必ずしも。不変のデータを持つことの利点は、それを共有できることです。したがって、コンパイラは、このような場合にxsを共有することで最適化できます。したがって、サイズはc++の場合と同じままです。

または、どういうわけか怠惰な呼び出しは、最後に1つの要素のみを追加することによって、実際にxsが返されることを確認しますか？

怠惰とは、値が実際に必要なときに評価することを意味し、メモリ使用量の削減を保証するものではありません。一方、怠惰のために作成されたサンクは、より多くのメモリを使用する可能性があります。

私はモナドが副作用をもたらす可能性のある何かを持つ方法であることを知っています。しかし、Monadを使用して、入力を変更し、その値を返すことはできますか？

あなたは部分的に正しいです。モナドは、副作用のあるコードを作成するために使用されます。可変ベクトルを非常にうまく使用して、IOモナドのc++の例と非常によく似たコードを書くことができます。

また、xs ++ [a]をa：xsに変更すると、消費するメモリが少なくなりますか？

これはコンパイラに依存しますが、リスト全体をコピーして最後に要素を追加すると思います。（私はこれの専門家ではありません）。

いつでもコードのプロファイルを作成し、メモリ消費量を確認できます。これは、これを学ぶための最良の方法です。

于 2012-12-20T15:08:13.550 に答える
1

言語が異なれば共通のイディオムも異なり、実装者はこれらのイディオムを可能な限り効果的にするように努めます。何かがC++で余分なオーバーヘッドを伴うため、別の言語で最も効果的なイディオムがC ++で最も効果的であるとは思わないのと同じように、別の言語でも同じことが当てはまるとは思いません。

そうは言っても、私は現在、頻繁に戻ってくる大規模で高性能なアプリケーションに取り組んでいますがstd::vector、これが問題になることはありません。NRVOや移動セマンティクスのようなものは、これがC++でも非常に効率的である可能性があることを意味します。

于 2012-12-20T15:03:25.813 に答える