問題タブ [proof]

Haskellプラットフォームで取得するApplicative型クラスのすべてのHaskellインスタンスは、すべてのApplicative法を満たしていることが証明されていますか？はいの場合、それらの証明はどこにありますか？

Control.Applicativeのソースコードには、さまざまなインスタンスの適用法が適用されるという証拠が含まれていないようです。それはただそれを述べています

次に、コメントに法律を記載します。

他の型クラス（AlternativeとMonad）のインスタンスについても同様のケースを見つけました。

これらの図書館の利用者は、これらの法律を自分で確認することになっていますか？

しかし、私はこれらの法律の厳格な証拠が開発者によって他の場所で与えられたのかどうか疑問に思いましたか？

繰り返しになりますが、IO MonadのApplicate（またはMonad）法の厳密な証明には、一般に、外部との会話が含まれるため、非常に複雑になる可能性があることを認識しています。

ありがとう。

質問の補題の違いを学んでいます。私が見つけることができるすべての参照は、例を使用しています:

両者の違いを示します。通常のレンマを使用してそれを「反証」する例を見つけることができます。

w = uvxyz, st |vy| を選択します。> 0、|vxy| <= p。w に同数の b、c、d が含まれているとします。

私が選んだのは：

y をポンピングすると、a の数が増えるだけで、|b|=|c|=|d| の場合 最初は、今でもそうです。

( w に a がない場合の同様の議論。その後、必要なものを何でもポンピングします。)

私の質問は、Ogden の補題がこの戦略をどのように変えるかということです。「マーキング」は何をしますか？

ありがとう！

私は Comb Sort についていくつかの調査を行っており、アルゴリズムが正しいことが証明されているかどうかを把握しようとしています。ただし、アルゴリズムに関する多くのドキュメントを見つけることができないようです。これは非常に単純なアルゴリズムですが、基本的にはバブル ソートの変形であり、証明は複雑ではないと思います。これに関する詳細情報をどこで見つけることができるか、またはそれを最初から証明する方法について考えている人はいますか?

Comb Sort に慣れていない方のために、ウィキペディアの記事で疑似コードを見つけることができます。

代数法則の観点から考えると、代数と同様に、ビット操作の領域に存在する公式のガイドラインがあるかどうか疑問に思っていました。

代数の例

a - b =/= b - a

させa = 7てb = 5

• a - b = 2
• b - a = -2

させa = 10てb = 3

• a - b = 7
• b - a = -7

したがってif a > b、b - aは に相当する負の値になりa - bます。このため、と言えます

|a - b| = |b - a|。

どこ|x|で の絶対値を示しますx。

ビット単位の例

a | b =/= a + b

符号なしバイト操作に注意してください:10 | 5 = 15と同義です。10 + 5 = 15

ただし、両方aとbが 5 に等しい場合OR、結果は 5 になりa = bます。これは、まったく同じビットを互いに比較しているだけであるため、新しい結果は何もないことを意味します。

同様に、 の場合b = 7、それらa = 10をOR15 にします。これは、

したがって、効果的にそれを結論付けることができa | b =/= a + bます。

applicative functor は構成下で閉じているが、モナドは閉じていないことはよく知られています。しかし、モナドが常に構成するとは限らないことを示す具体的な反例を見つけるのに苦労しています。

この回答は[String -> a]、非モナドの例です。少しいじってみたところ、直感的にそう思いますが、その答えは「結合は実装できません」というだけで、正当な理由はありません。もっとフォーマルなものをお願いします。もちろん、 type を持つ関数はたくさんあります[String -> [String -> a]] -> [String -> a]。そのような関数はモナドの法則を必ずしも満たさないことを示さなければなりません。

どんな例でも（付随する証拠とともに）実行できます。特に上記の例の証明を探しているわけではありません。

帰納法を使用して二分木のプロパティを証明するのに問題があります。

私のセットアップは正しいですか？もしそうなら、どうすればこれらのものを実際に見せることができるでしょうか。私が試したことはすべて、結局めちゃくちゃになりました。助けてくれてありがとう

次の定義を前提としています (最初の 2 つはhttp://www.cis.upenn.edu/~bcpierce/sf/Basics.htmlから取得したものです)。

次のことを証明したいと思います。

私が到達できた最も遠いところは、 とblt_nat_flip仮定して証明することblt_nat_flip0です。私は多くの時間を費やし、ほとんどそこにいますが、全体的には必要以上に複雑に見えます. 2つの補題を証明する方法について、より良いアイデアを持っている人はいますか?

これまでの私の試みは次のとおりです。

よくあるプログラミング インタビューの問題に出くわしました。符号なし整数のリストが与えられたとき、リスト内で奇数回出現する 1 つの整数を見つけます。たとえば、次のリストが与えられた場合:

他の整数は偶数回発生するのに対し、リスト内で 3 回発生するため、解は整数 5 になります。

私の最初の解決策は、並べ替えられた配列を設定し、配列を反復処理することでした。奇数要素ごとに整数を加算し、偶数要素ごとに減算します。他の整数が相殺されるため、最終合計が解決策でした。

しかし、各要素に対して XOR を実行するだけで、より効率的な解決策が存在することがわかりました。並べ替えられた配列は必要ありません。つまり、次のようになります。

私が取った Discrete Structures クラスから、Associate Property が XOR 操作に適用できることを思い出しました。それが、このソリューションが機能する理由です。

と：

連想プロパティが XOR で機能することは覚えていますが、XOR に固有のこのプロパティの論理的証明を見つけるのに苦労しています (インターネット上のほとんどの論理的証明は、AND 操作と OR 操作に重点を置いているようです)。連想プロパティが XOR 操作に適用される理由を知っている人はいますか?

AND および/または OR を含む XOR ID が含まれていると思われます。

ラムダ項 (λx.y)((λx.xxx)(λx.xxx)) を実際に計算する言語の選択方法 つまり、通常の順序削減と弱い型システムに言語が必要です。

この最適化問題のコンピュータの複雑さを証明しようとしています:
連結グラフ G = (V, E) と集合 S ⊊ V が与えられた場合、連結部分グラフ G'= (V', E ') を見つけます。

対象:

すべての頂点をツリーに含める必要がない場合、最小スパニング ツリー問題の一般化のように見えます。この問題の複雑さを還元によって証明するために使用できる既知の問題はありますか?