問題タブ [referential-transparency]

Haskell について私が魅力的だと思うことの 1 つは、関数と変数がどのように同じであるかということです。ほとんどの言語では、関数が何かを実行している間、変数は値を保持し、最終的に値を返します。Haskell ではこの違いは見られず、Haskell を使用した後、変数が関数やメソッドとは異なる、より「伝統的な」プログラミングに戻るのはぎこちなく感じます。値を取得したい場合、それが定数値であるか、変更可能な変数であるか、複雑な計算の結果であるかに関係なく、その元を気にする必要はありません。Haskell では、変数は単なる 0-ary 関数です。

多くのオブジェクト指向言語には、少しギャップを感じさせるプロパティがあります。

Haskell に似たシステムを持つ他の言語を示すことができる人はいますか? 参照透過性のために関数型言語に共通していると思っていましたが、そうではないことがわかりました。たとえば Lisp では、(defun)関数を明示的に宣言する必要があります。

言い換えれば、永続データ構造の多対多の関係を効率的にモデル化できますか？

一方向のマルチマップのペアが提案されました。ただし、これが永続データ構造での削除にどのように機能するかはわかりません。キー1..4から値"1".. "4"があり、それぞれが他のすべてを参照しているとすると、両方向で非常によく似た2つのマップがあります。

{1 => ["2"、 "3"、 "4"]、2 => ["1"、 "3"、 "4"]、...} {"1" => [2,3、 4]、 "2" => [1,3,4]、...}

次に、アイテム1をシステムから完全に削除します。これには、最初のマップで1つのノードを変更する必要がありますが、2番目のマップでn-1ノードを変更する必要があります。数千のnの場合（これを検討している場合は可能性が高いです）、それはかなり高価ではないでしょうか？または、マルチマップはそのタイプの変更を処理するために最適化されていますか？病的なケースですが、それでも...

四分木は魅力的なアイデアのようです。もう少し考えてみます。

Word32、String (カリー化は無視) などのいくつかのパラメーターを取り、IO Word32 を出力する関数を haskell で作成しました。さて、これは真の意味での関数です:同じ入力に対して、出力は常に同じになります. 副作用はありません。関数が Word32 ではなく IO Word32 を返す理由は、関数が多くの 32 ビット リニア フィードバック シフト レジスタ (lfsr) およびその他のレジスタをループ内で数回更新して、最終的な Word32 出力を計算するためです。

私の質問は次のとおりです。この関数には実質的に副作用がないことを考えると、関数がIO Word32ではなくWord32を返すように、関数実装内でこれらのレジスタ更新を非表示にすることは可能ですか? もしそうなら、どのように？

この質問について正確に何をグーグルするかわからないので、SOに直接投稿します：

1. Haskell の変数は不変です
2. 純粋な関数は、同じ引数に対して同じ値になる必要があります

somePureFunc somevar1 somevar2これら 2 つの点から、コードを 2 回呼び出した場合、最初の呼び出し時に値を計算することだけが意味があると推測できます。結果の値は、ある種の巨大なハッシュ テーブル (またはそれに類するもの) に格納でき、その後の関数呼び出しで参照できます。2 つの質問があります。

1. GHC は実際にこのような最適化を行っているのでしょうか?
2. もしそうなら、結果を調べるよりも計算を繰り返す方が実際に安価な場合の動作は何ですか?

ありがとう。

I'm trying to reconcile the definition of referential transparency with how OCaml handles polymorphic types and side-effects. I read on https://web.archive.org/web/20120729232358/http://www.csc.villanova.edu/~dmatusze/resources/ocaml/ocaml.html that

A definition is said to have referential transparency if its meaning does not depend on the context it is in. Functions in OCaml have referential transparency, that is, changing the context (other variables and other functions) does not change the meaning of any functions you have already defined. This fact can be crucial when you are debugging a program, because you are likely to be redefining functions fairly frequently.

But the way I understand things, this can't be true in OCaml because it is possible to perform a whole bunch of side-effects (like writing to files and performing other calculations) before returning whatever was fed into the function.

You could potentially have a function f : string -> string so that f "a" does not equal f "a". We can drop in some side-effecting expressions into the body of the function that are completely invisible in the type description of f.

As an example f could be defined to return the first line of some file. There could be a function somewhere in the context of f that is changed which affects what first line f returns. Or worse, some function in the context could delete the file that f depends on which would make f undefined.

So is OCaml referentially transparent or am I missing something?

こんにちは、私は Haskell の初心者です。DeMorgan の法則を論理式に適用できる Haskell プログラムを作成したいと考えています。問題は、与えられた式を新しい式に変更できないことです (DeMorgan の法則を適用した後)

具体的には、私のデータ構造です

「LogicalExpression」を受け取り、DeMorgan の法則を適用した後に「LogicalExpression」を返す関数を作成したいと思います。

たとえば、このパターンを見つけるたびに: Neg ( Conj (Var 'a') (Var 'b') ) in a logicalExpression, Conj ( Neg (Var 'a') Neg (Var 'b') に変換する必要があります）。

アイデアは単純ですが、haskell で実装するのは非常に難しいです。x を検索して y に変換する関数 (Z と呼びましょう) を作成しようとするようなもので、Z に "vx" を指定すると、それは "vy" に変換されます。文字列の代わりにデータ構造「logicalExpression」を取り、x の代わりに私が言及したパターンを取り、logicalExpression 全体を再び吐き出しますが、パターンは変更されています。

PS:関数が任意の複雑な論理式を取り、DeMorgan の法則を使用して単純化するようにしたい

ヒントはありますか？

前もって感謝します。

私は最近、Haskell の Monad - State を見てきました。このモナドで動作する関数を作成できましたが、動作をクラスにカプセル化しようとしています。基本的に、Haskell で次のようなものを複製しようとしています。

誰かがこれを手伝ってくれるなら、私はとても感謝しています。ありがとう！

ジェネレーターの次の 2 つの定義のどちらかを決定しようとしています。どちらが良いですか？「よりpythonic」なのはどれですか？そして、それぞれの欠点を軽減する方法はありますか?

最初のものは、ジェネレーターによって返された値を変更します。おそらく、私がまだ予見していなかった呼び出しコードを台無しにします。2 番目は、この場合、1000 タプル相当のガベージを生成します。「howMany」を増やすと (可能性があります)、それ以上になります。

例として挙げたループは、ジェネレーターの現在の使用にすぎません。そこから得られる値を保存することはないと思いますが、他の場所で役立つ可能性のあるちょっとしたユーティリティです。

putStrLn引数を指定して呼び出すと、常にタイプの値が返されますIO ()。私はそれが純粋であることに同意します、私はそれを扱うことができます。しかし、それは参照透過性ですか？私はそう思います。なぜなら、与えられた入力に対して、関数呼び出しをIO ()stdoutで正しい文字列をスローするanに置き換えることができるからです。

だから私は。でかっこいいですが、引数なしで呼び出されputStrLnたとき、それらがタイプであるならば、いくつものものを返すことができます。それは純粋でも参照透過性でもありませんよね？getLineIO String

ばかげた衒学的な質問で、コードの書き方はおそらく変わらないでしょうが、私は本当にこれを完全に釘付けにしたいのです。（IOモナドが物事を正しくシーケンスすることを理解しています。それは私の問題ではありません）

これは私に別の質問を提起します。コンパイラは、入力を受け取らないプログラムを認識するのに十分賢いですか？たとえば、私がコンパイルするとします

IO ()GHCは、そのプログラムを[2,3,4,5,6,7,8,9,10,11]が出力されるように減らすのに十分賢いですか？それとも、それでもうまくいき、実行時にすべてを評価/実行しますか？入力が不要な任意のプログラムについても同様です。GHCは、プログラム全体が参照透過性であり、その価値に簡単に置き換えることができるという事実を採用していますか？

次のようなプログラムがあるとしましょう:

これをコンパイルして、実行可能ファイルが 50000005000000 を出力するだけで、それほど時間と労力をかけないようにしたいと考えています。

基本的に、確実に計算される式 (ここでは厳密性分析が役立つかもしれません) は、コンパイル時に事前に計算できます(つまり、参照透過性を使用して、値を計算するときに実際には問題にならないことを示します)。

要するに：「計算する必要があります」+参照透過性=事前に計算できます

これは、入力に依存する何かに到達するまでプログラムを実行するようなものです (つまり、すべての入力に共通するプログラムのコアは事前に計算されます)。

現在これを達成するための既存のメカニズムはありますか (Haskell または他の言語で)? [そもそも参照透過性がないため、C++ のテンプレートのようなものを指さないでください。]

そうでない場合、この問題はどれほど難しいですか? [付随する技術的 (および理論的) 問題は何ですか?]