問題タブ [lambda-calculus]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
lambda - 関数適用を実装したラムダ計算式
次のラムダ計算式を見つけました。
つまり、これは引数 f を取り、引数 x を取り、x を f に適用した結果を生成する別の関数を返す関数です。上記の式の結果は (λ b . b) になります。
これは部分適用とカリー化を思い起こさせますが、「インサイド アウト」関数適用 (fx) が私の興味をそそりました。
その表現には、より深い理論的な意味がありますか?
lambda-calculus - ネーミングコンテキストを使用して、自由変数のドブラウンインデックスを見つける方法は?
「タイプとプログラミング言語」のセクション6.1.2では、ラムダ式の自由変数に番号を付けるために使用されるネーミングコンテキストについて説明しています。彼らが提供したスキームの例を使用すると、両方ともλx.xb
、明らかに異なる用語である場合のように、 λx.xx
deBruijn表現を持ちます。λ.00
これはどのように作動しますか?
haskell - 構文木をモジュロアルファ変換で比較する
私はコンパイラ/プルーフチェッカーに取り組んでいますが、次のような構文ツリーがあるかどうか疑問に思っていました。たとえば、次のようになります。
sのアルファ等価性(等価モジュロ名前変更)をチェックする方法があった場合Expr
。ただし、これExpr
はラムダ計算とは異なり、ラムダ内の変数のセットは可換です。つまり、パラメーターの順序はチェックに考慮されません。
(ただし、簡単にするために、とLambda ["x","y"] ...
は異なりLambda ["x"] (Lambda ["y"] ...)
ます。その場合、順序は重要です)。
言い換えると、2つが与えられたExprs
場合、1つが一方から他方への名前変更を効率的に見つけるにはどうすればよいでしょうか。この種の組み合わせ問題は、NP完全のにおいがします。
types - Hindley Milner で表現できない system-f のいくつかのタイプおよび/または用語は何ですか?
Hindley Milner が system-f の制限であるとどこかで読んだことを覚えています。その場合、system-f では入力できるが HM では入力できない用語を誰か教えてください。
haskell - コンビネータの型シグネチャが、同等のLambda関数の型シグネチャと一致しません
このコンビネータを考えてみましょう。
引数XYに適用します。
それは以下に契約します:
S(SK)を対応するラムダ項に変換し、次の結果を得ました。
Haskell WinGHCiツールを使用して(\ xy-> xy)の型アノテーションを取得すると、次のように返されます。
それは私には理にかなっています。
次に、WinGHCiを使用してs(sk)の型シグネチャを取得すると、次のように返されます。
それは私には意味がありません。型アノテーションが異なるのはなぜですか?
注:s、k、およびiを次のように定義しました。
haskell - このコンビネータは何をしますか:s(sk)
私は今、次の型署名を理解していますs (s k)
:
そして、HaskellWinGHCiツールでエラーなしで機能する例を作成できます。
例:
を返します2
。
例:
を返します4
。
ここsuccessor
で、次のように定義されます。
それにもかかわらず、私はまだ何をするのかについて直感的な感覚s (s k)
を持っていません。
コンビネータs (s k)
は、任意の2つの関数f
とを取りますg
。とは何s (s k)
をf
しg
ますか?何をお願いするかについての全体像を教えていただけますs (s k)
か?
haskell - Haskell の教会リスト
次のように定義されている教会リストを操作するには、haskell マップ関数を実装する必要がありました。
ラムダ計算では、リストは次のようにエンコードされます。
この演習のサンプル ソリューションは次のとおりです。
このソリューションがどのように機能するのかわかりませんし、そのような関数を作成する方法もわかりません。私はすでにラムダ計算と教会数の経験がありますが、この演習は私にとって大きな頭痛の種であり、来週の試験のためにそのような問題を理解して解決できなければなりません. そのような問題を解決する方法を学ぶことができる良い情報源を教えてください。または、それがどのように機能するかについて少しガイダンスを教えてください
scheme - スキームのラムダ削減の改善
形式が不十分だったので、この質問を書き直しています。
ラムダ式でラムダ削減を行う上記のコードがあります(これが私が欲しいものです)。ここでの私の問題は、誰かがこの実装を書き直すのを手伝ってくれることです(私はSchemeの経験がないので)。これにより、本体からアルファ変換を行う部分を抽出し、それを別の関数に入れます。ベータ還元も。関数 reduce は再帰的であるため、新しく作成された 2 つの関数は single-step である必要があります。つまり、1 つの境界付き変数のみを変換し、1 つの式のみを還元します。
haskell - Haskellの教会リストの操作
ラムダ計算では、リストは次のようにエンコードされます。
チャーチリストに実装できる他のリスト関数について考えており、2つのチャーチリストを連結するconc2関数を正常に作成しました。
また、通常のリストでzipWithのように動作するzipWithChurchも試しました。しかし、私は解決策を見つけることができません。誰か助けてもらえますか?
haskell - ラムダ計算で解が見つかったら、これをコードに変換するのはどれくらい簡単ですか?
TopCoder で見つかったような問題文を読んで、それをラムダ計算表現に変換した場合、これを Haskell または Lisp コードに「変換」するのは簡単な演習ですか?
言い換えれば、ラムダ計算形式システムを使用して問題を解決し、関数型プログラミング言語で自明に実装できるでしょうか?