haskell - Haskell: タイプ a -> a の関数の例、恒等式以外

Question

私は Haskell で少し遊んで始めたばかりです... ID の同じ型の関数を書きたいです。明らかに、それと同等ではありません。それは次のようなものです。

myfunction :: a -> a

パラメーターと戻り値の型が同じで、事実上何でもかまいません (これは、Haskell の Typeclasses を使用する可能性を排除します)。

Answer 1

undefinedこれは、言及された別のコメンターとして使用しないと不可能です。反例で証明してみましょう。そのような関数があったと仮定します:

f :: a -> a

それは と同じではないと言うとき、それidは定義できないことを意味します:

f x = x

aただし、が typeの場合を考えてみましょう():

f () = ...

f返される可能性のある唯一の結果は()ですが、それは と同じ実装idになるため、矛盾します。

より洗練された厳密な答えは、型a -> aが と同型でなければならないことを示すこと()です。a2 つの型が同形であると言うときb、それは 2 つの関数を定義できることを意味します。

fw :: a -> b
bw :: b -> a

... そのような：

fw . bw = id
bw . fw = id

a -> a最初のタイプがで、2 番目のタイプが の場合、これを簡単に行うことができます()。

fw :: (forall a . a -> a) -> ()
fw f = f ()

bw :: () -> (forall a . a -> a)
bw () x = x

次に、次のことを証明できます。

fw . bw
= \() -> fw (bw ())
= \() -> fw (\x -> x)
= \() -> (\x -> x) ()
= \() -> ()
= id

bw . fw
= \f -> bw (fw f)
-- For this to type-check, the type of (fw f) must be ()
-- Therefore, f must be `id`
= \f -> id
= \f -> f
= id

2 つの型が同型であることを証明すると、1 つの型に有限数の要素が存在する場合、もう 1 つの型にも有限数の要素が存在することがわかります。型()には 1 つの値だけが存在するため、次のようになります。

data () = ()

つまり、型(forall a . a -> a)にはちょうど 1 つの値が存在する必要があることを意味します。これはたまたま の実装ですid。

編集: 一部の人々は、同形の証明が十分に厳密ではないとコメントしているので、Haskell に翻訳すると、任意のファンクターについて次のように言う米田補題を呼び出しますf。

(forall b . (a -> b) -> f b) ~ f a

whereは に同形である~ことを意味します。ファンクターを選択すると、これは次のように単純化されます。(forall b . (a -> b) -> f b)f aIdentity

(forall b . (a -> b) -> b) ~ a

... を選択するとa = ()、次のようにさらに単純化されます。

(forall b . (() -> b) -> b) ~ ()

() -> bが に同型であることは簡単に証明できますb。

fw :: (() -> b) -> b
fw f = f ()

bw :: b -> (() -> b)
bw b = \() -> b

fw . bw
= \b -> fw (bw b)
= \b -> fw (\() -> b)
= \b -> (\() -> b) ()
= \b -> b
= id

bw . fw
= \f -> bw (fw f)
= \f -> bw (f ())
= \f -> \() -> f ()
= \f -> f
= id

したがって、それを使用して、最終的に米田同型を次のように特殊化できます。

(forall b . b -> b) ~ ()

これは、 type の関数forall b . b -> bは に同形であると言っています()。米田の補題は、私の証明が欠けていた厳密さを提供します。

Answer 2

dbaupp のコメントを詳しく説明する回答を作成させてください。type の関数は、 typea -> aの関数も() -> ()生成するため、最初にこの部分問題を見ていきます。

Haskell の型と関数の通常のセマンティクスは、型を先のとがったチェーン完全な半順序として表し、関数を連続関数として表します。型は、順序⊥⊏()()を持つ2 つの要素セット{⊥,()}によって表されます。単純な集合論では、この集合からそれ自体への関数は 2^2=4 ありますが、連続しているのはそのうちの 3 つだけです。

• f1: ⊥ ↦ ⊥, () ↦ ⊥,
• f2: ⊥ ↦ ⊥、() ↦ ()、および
• f3: ⊥ ↦ (), () ↦ ().

したがって、セマンティック モデルには、 type の 3 つの異なる関数があり() -> ()ます。しかし、Haskell で実装できるのはどれでしょうか? それらのすべて！

• f1 _ = undefined(またはf1 x = f1 x)
• f2 x = x(またはf2 = id)
• f3 _ = ()(またはf3 = const ())

これらの定義を見ると、f1とf2を使用して type の関数を定義することもできることがわかりますa -> a。彼らはすでに別のことをして()いるので、彼らは異なっています。したがって、 type の少なくとも 2 つの異なる関数がありa -> aます。

上記のセマンティック モデルには、より多くの type の関数がありますa -> aが、これらは Haskell では表現できません (これは、パラメトリック性と Wadler のFree の定理に関連しています)。f1とが唯一のそのような関数であるという適切な証明f2は、Haskell 言語が何を許可しないか (たとえば、引数の型でパターン マッチングを行わないこと) に依存するため、あまり簡単ではないように思われます。

Answer 3

undefined または bottom (非終了式) を使用する意思がない限り、そのタイプを満たす関数は文字通り他にありません。

これは Haskell 型システムの大きな強みの 1 つです。コンパイラを通過できる可能性のある関数を、明らかに正しい関数に限定することができます。極端な例については、djinnを参照してください。これは型を取り、その型に一致する可能な関数を生成します。実際の複雑な例であっても、多くの場合、リストは非常に短いものです。

Answer 4

ここで重要なのは、 について何も知らないaことを理解することです。特に、新しいものを生成したり、別のものに変換したりする方法はありません。したがって、それ (または最低値) を返すという選択肢はありません。(コンテキスト バインドなど)に関する情報が増えるとすぐに、aそれを使ってさらに興味深いことができます。

f :: Monoid a => a -> a
f _ = mempty

また

f :: Monoid a => a -> a
f x = x `mappend` x `mappend` x

または、 のような選択肢がある場合は、f :: (a, a) -> a2 つの可能な実装があります (最下位の値を再び無視します) が、f :: (a, b) -> a1 つの実装に戻ります。これは for とfst同じfです。の実装では、両方の引数の型が同じかどうかをテストする方法がないため、 が のように動作するf ("x", "y")ことを確認できます。同様に、 の非ボトム バージョンは 1 つだけです。ffstff :: (a -> b) -> a -> b

ポリモーフィズムは自由度を制限します。これは、引数について何も知らないためであり、場合によっては、底のない 1 つのバージョンに要約されます。

Answer 5

他の人が述べたように、そのような他の合計関数は存在できません。(total 関数に限定しない場合は、任意の型を by で使用できundefinedます。)

λ計算に基づいて理論的な説明をしようと思います。

簡単にするために、λ項に制限しましょう (Haskell 式を翻訳できます)。λ タームの場合、そのヘッドif and is not an application (ゼロでもかまいません)をM呼び出しましょう。が通常の形式の場合、 でない限り、λ 抽象化できないことに注意してください。AM ≡ A N1 ... NkAkMAk = 0

したがってM :: a -> a、 を正規形の λ 項とします。コンテキストに変数Mがないため、変数にすることも、アプリケーションにすることもできません。もしそうなら、その頭は変数でなければなりません。したがってM、 は λ 抽象である必要があり、 である必要がありますM ≡ λ(x:a).N。

現在は、正式にNは のタイプである必要があります。が λ 抽象化の場合、その型は になりますが、これは不可能です。が関数アプリケーションの場合、その head は変数でなければならず、コンテキスト内にあるのは だけです。しかし、は何にも適用できないため、任意の P に対してテープ可能ではありません。したがって、唯一の可能性は です。だから、でなければなりません。a{x:a}⊢N:aNσ -> τNxx:axx PN ≡ xMλ(x:a).x

_{（可能であれば、私の英語を修正してください。特に、接続法の権利の使い方がわかりません）。}