357

forall次のように、いわゆる「存在型」でキーワードがどのように使用されるかを理解し始めています。

data ShowBox = forall s. Show s => SB s

ただし、これは がどのように使用されるかのサブセットにすぎず、次のforallような用途での使用に頭を悩ませることはできません。

runST :: forall a. (forall s. ST s a) -> a

または、これらが異なる理由を説明します。

foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

それとも全部RankNTypes...

私は、アカデミックな環境で普通に使われている種類の言語よりも、明確で専門用語のない英語を好む傾向があります。私がこれについて読もうとしている説明のほとんど (検索エンジンで見つけることができるもの) には、次のような問題があります。

  1. それらは不完全です。runST彼らは、このキーワードの使用の一部 (「存在型」など) を説明しており、それをまったく異なる方法で使用するコード (や上記など)fooを読むまで、私は幸せに感じます。bar
  2. それらは、離散数学、圏論、または抽象代数の今週人気のある分野の最新のものを私が読んだという仮定がぎっしりと詰め込まれています。(「実装の詳細については論文を参照してください」という言葉を二度と読まなければ、早すぎます。)
  3. それらは、単純な概念でさえ、曲がりくねってねじれ、断片化された文法と意味論に頻繁に変わる方法で書かれています。

そう...

実際の質問に進みます。forall私が専門用語にどっぷりと浸かっている数学者であると想定しない、明確で平易な英語でキーワードを完全に説明できる人はいますか?


追加するために編集:

以下のより質の高いものから2つの際立った回答がありましたが、残念ながら私は1つだけを最高のものとして選ぶことができます. ノーマンの答えは詳細で有用であり、理論的基盤のforallいくつかを示すと同時に、それの実際的な意味のいくつかを示す方法で物事を説明しました. ヤルチュの答え誰も言及していない領域 (スコープ型変数) をカバーし、すべての概念をコードと GHCi セッションで説明しました。両方を最良のものとして選択することが可能であれば、私はそうします. 残念ながらできません。両方の回答を詳しく調べた後、例示的なコードと添付の説明のために、yairchu のほうが Norman のものよりわずかに優れていると判断しました。ただし、これは少し不公平です。実際には、これを理解するために両方の答えが必要だったのでforall、型シグネチャで見たときにかすかな恐怖感を残さないほどです。

4

8 に答える 8

301

コード例から始めましょう。

foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
foob postProcess onNothin onJust mval =
    postProcess val
    where
        val :: b
        val = maybe onNothin onJust mval

このコードは、単純な Haskell 98 ではコンパイルされません (構文エラー) forall。キーワードをサポートするには拡張機能が必要です。

基本的に、キーワードには 3 つの異なる一般的な使用法がありforall(または、少なくともそう思われます)、それぞれに独自の Haskell 拡張があります: ScopedTypeVariables, RankNTypes/ Rank2Types, ExistentialQuantification.

上記のコードは、これらのいずれかが有効になっていても構文エラーを取得しませんが、有効になっている型チェックのみを取得しますScopedTypeVariables

スコープ型変数:

スコープ型変数は、where句内のコードの型を指定するのに役立ちます。bval :: b同じものをb作りますfoob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b

紛らわしい点forall:型から を省略しても、実際にはまだ暗黙的にそこにあると聞くかもしれません。(ノーマンの回答から:「通常、これらの言語は多態型から forall を省略します」)。この主張は正しいforall、 の使用ではなく、 の他の使用について言及してScopedTypeVariablesいる。

ランク N タイプ:

が有効な場合を除いて、mayb :: b -> (a -> b) -> Maybe a -> bと同等のものから始めましょう。mayb :: forall a b. b -> (a -> b) -> Maybe a -> bScopedTypeVariables

これは、すべてのaおよびに対して機能することを意味しbます。

このようなことをしたいとしましょう。

ghci> let putInList x = [x]
ghci> liftTup putInList (5, "Blah")
([5], ["Blah"])

this の型は何liftTupですか? ですliftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)。その理由を確認するために、コード化してみましょう。

ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b)
ghci> liftTup (\x -> [x]) (5, "Hello")
    No instance for (Num [Char])
    ...
ghci> -- huh?
ghci> :t liftTup
liftTup :: (t -> t1) -> (t, t) -> (t1, t1)

「うーん..タプルには同じ型が2つ含まれている必要があるとGHCが推論するのはなぜですか?それらがそうである必要はないことを伝えましょう」

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

うーん。ここで GHC は、 とが必要なため、申請liftFuncを許可しません。私たちの関数は、あらゆる可能性を受け入れる関数を取得したいのです!vv :: bliftFuncxx

{-# LANGUAGE RankNTypes #-}
liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

したがってliftTup、すべてxの場合に機能するわけではなく、機能するのは取得する機能です。

実存的定量化:

例を使用しましょう:

-- test.hs
{-# LANGUAGE ExistentialQuantification #-}
data EQList = forall a. EQList [a]
eqListLen :: EQList -> Int
eqListLen (EQList x) = length x

ghci> :l test.hs
ghci> eqListLen $ EQList ["Hello", "World"]
2

N型との違いは?

ghci> :set -XRankNTypes
ghci> length (["Hello", "World"] :: forall a. [a])
    Couldnt match expected type 'a' against inferred type '[Char]'
    ...

Rank-N-Types では、式がすべての可能なsforall aに適合する必要があることを意味しました。a例えば:

ghci> length ([] :: forall a. [a])
0

空のリストは、どのタイプのリストとしても機能します。

したがって、存在量化では、定義forall内の s は、含まれる値がすべての適切な型である必要があるのではなく、任意の適切な型である可能性があることを意味します。data

于 2010-06-18T17:44:06.940 に答える
135

forall キーワードを明確で平易な英語で完全に説明できる人はいますか?

いいえ(まあ、ドン・スチュワートならできるかもしれません。)

シンプルで明確な説明または の障壁は次のforallとおりです。

  • 数量詞です。普遍的または存在量指定子を見たことがあるには、少なくとも少しの論理 (述語計算) が必要です。述語計算を見たことがない、または量指定子に慣れていない場合 (そして、博士課程の資格試験中に、慣れていない学生を見たことがあります) には、 について簡単に説明することはできませんforall

  • 量指定子です。System Fを見たことがなく、ポリモーフィック型を書く練習をしたことがない場合は、forall混乱するでしょう。Haskell や ML の経験は十分ではありません。通常、これらの言語ではforallポリモーフィック型が省略されるためです。(私の考えでは、これは言語設計の間違いです。)

  • 特に Haskell では、forall私が紛らわしいと思う方法で使用されています。(私は型理論家ではありませんが、私の仕事は多くの型理論に触れさせてくれます。私はそれに慣れています。) 私にとって、混乱の主な原因はforall、型をエンコードするために使用されるものです。私自身は で書きたいと思いexistsます。これは、量指定子と矢印を含む型の同型化のトリッキーなビットによって正当化されます。それを理解したいと思うたびに、自分で調べて同型化を解決する必要があります。

    型同型の考え方に慣れていない場合、または型同型について考える習慣がない場合、この の使用はforallあなたを困惑させるでしょう。

  • の一般的な概念forall(型変数を導入するためのバインド) は常に同じですが、さまざまな用途の詳細は大きく異なる場合があります。インフォーマルな英語は、バリエーションを説明するのにあまり適していません。何が起こっているのかを本当に理解するには、数学が必要です。この場合、関連する数学は Benjamin Pierce の入門テキスト「Types and Programming Languages」に記載されています。これは非常に優れた本です。

あなたの特定の例については、

  • runST 頭が痛くなるはずです。上位のタイプ (矢印の左側) は、野生ではめったに見つかりません。「Lazy Functional State Threads」を紹介した論文を読むことをお勧めしrunSTます。これは非常に優れた論文であり、特に の型と高ランクの型全般について、はるかに優れた直感が得られます。説明は数ページに及びますが、非常によくできていて、ここで要約するつもりはありません。runST

  • 検討

    foo :: (forall a. a -> a) -> (Char,Bool)
    bar :: forall a. ((a -> a) -> (Char, Bool))
    

    を呼び出すとbar、好きなタイプを簡単に選択でき、 type から typeへaの関数を渡すことができます。たとえば、関数または関数を渡すことができます。は、 「タイプを選択できるようになりました」と言っていると考えることができます。(型を選択するための専門用語はインスタンス化です。)aa(+1)reverseforall

    呼び出しに関する制限fooはより厳しく、 への引数は多相関数でfoo なければなりません。そのタイプでは、渡すことfooができる唯一idの関数は、undefined. その理由は、fooの場合、 is が矢印の左側にあるため、 Iforallの呼び出し元がis を選択するのではなく、 it の実装がisを選択するからです。は のように矢印の上ではなく、矢印の左側にあるため、インスタンス化は呼び出しサイトではなく関数の本体で行われます。fooafooaforallbar

要約:キーワードの完全な説明にforallは数学が必要であり、数学を学んだ人だけが理解できます。部分的な説明であっても、数学がなければ理解するのは困難です。しかし、私の部分的で非数学的な説明が少し役立つかもしれません。Launchbury と Peyton Jones を読んでくださいrunST


補遺:「上」、「下」、「の左側」という専門用語。これらは、型が記述されるテキストの方法とは何の関係もなく、抽象構文ツリーと関係があります。抽象構文では、aforallは型変数の名前を取り、forall の「下」に完全な型があります。矢印は 2 つの型 (引数と結果の型) を取り、新しい型 (関数型) を形成します。引数の型は矢印の「左側」です。これは、抽象構文ツリー内の矢印の左の子です。

例:

  • ではforall a . [a] -> [a]、forall は矢印の上にあります。矢印の左側にあるのは です[a]

  • forall n f e x . (forall e x . n e x -> f -> Fact x f) 
                  -> Block n e x -> f -> Fact x f
    

    括弧内のタイプは「矢印の左側の forall」と呼ばれます。(私が取り組んでいるオプティマイザーでこのような型を使用しています。)

于 2010-06-18T16:19:23.050 に答える
57

私の最初の答え:

誰もがforallキーワードを明確でわかりやすい英語で完全に説明できますか

ノーマンが指摘しているように、型理論から専門用語を明確でわかりやすい英語で説明することは非常に困難です。私たちは皆、努力しています。

'forall'について覚えておくべきことは本当に1つだけです。それは、型をあるスコープにバインドします。それを理解すれば、すべてがかなり簡単です。これは、タイプレベルでの「ラムダ」(または「let」の形式)に相当します。ノーマンラムゼーは、「左」/「上」の概念を使用して、この同じスコープの概念を優れた回答で伝えています。

'forall'のほとんどの使用法は非常に単純であり、GHCユーザーマニュアルS7.8で紹介されています。特に、 'forall'のネストされた形式の優れたS7.8.5です。

Haskellでは、タイプが普遍的に定量化されている場合、通常、タイプのバインダーを省略します。

length :: forall a. [a] -> Int

と同等です:

length :: [a] -> Int

それでおしまい。

型変数を特定のスコープにバインドできるようになったため、最初の例のように、型変数がデータ構造内でのみ表示されるトップレベル(「全称記号」)以外のスコープを持つことができます。これにより、非表示の型(「実存型」)が可能になります。または、バインディングを任意にネストすることもできます(「ランクNタイプ」)。

型システムを深く理解するには、専門用語を学ぶ必要があります。それがコンピュータサイエンスの本質です。ただし、上記のような単純な使用法は、値レベルの「let」との類推により、直感的に把握できる必要があります。素晴らしい紹介は、ローンチブリーとペイトンジョーンズです。

于 2010-06-18T18:02:44.673 に答える
35

これは、あなたがすでに慣れ親しんでいる可能性が高い、平易な言葉での簡単で汚い説明です。

このforallキーワードは、Haskell では実際には 1 つの方法でしか使用されません。いつ見ても同じ意味です。

普遍的な定量化

全称量化型は、フォームの型ですforall a. f a。その型の値は、引数として型を取り、typeのを返す関数と考えることができます。Haskell では、これらの型引数は型システムによって暗黙的に渡されます。この「関数」は、受け取る型に関係なく同じ値を提供する必要があるため、値はポリモーフィックです。 af a

たとえば、タイプを考えてみましょうforall a. [a]。その型の値は別の型aを取り、同じ型の要素のリストを返しますa。もちろん、可能な実装は 1 つだけです。a絶対に任意のタイプになる可能性があるため、空のリストを提供する必要があります。空のリストは、その要素型が多態的である唯一のリスト値です (要素がないため)。

またはタイプforall a. a -> a。このような関数の呼び出し元は、型aと型の値の両方を提供しますa。次に、実装は同じ型の値を返す必要がありますa。可能な実装は 1 つだけです。与えられたのと同じ値を返す必要があります。

存在の定量化

Haskell がその表記法をサポートしている場合、存在量化された型は の形式になります。その型の値は、型と型の値で構成されるペアexists a. f a(または「製品」)と考えることができます。af a

たとえば、 type の値がある場合exists a. [a]、何らかのタイプの要素のリストがあります。どんなタイプでも構いませんが、それが何かわからなくても、そのようなリストに対してできることはたくさんあります。逆にすることも、要素の数を数えることも、要素の型に依存しないその他のリスト操作を実行することもできます。

わかりました、ちょっと待ってください。forallHaskellが次のような「存在する」型を示すために使用するのはなぜですか?

data ShowBox = forall s. Show s => SB s

紛らわしいかもしれませんが、実際にはデータ コンストラクターの型を SB記述しています。

SB :: forall s. Show s => s -> ShowBox

ShowBox構築されると、type の値は 2 つのもので構成されると考えることができます。typesの値を持つ typesです。つまり、存在量化型の値です。Haskell がその表記法をサポートしていれば、ShowBox実際には のように書くことができます。exists s. Show s => s

runSTと友達

それを考えると、これらはどう違うのですか?

foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

まず取りましょうbaratypeと type の関数を取り、 typea -> aの値を生成します(Char, Bool)。を として選択Intし、たとえばatype の関数を与えることができます。Int -> Intしかしfoo、違います。の実装では、foo指定した関数に任意の型を渡すことができる必要があります。したがって、合理的に与えることができる唯一の関数は ですid

の型の意味に取り組むことができるはずですrunST

runST :: forall a. (forall s. ST s a) -> a

そのため、どの型を として与えても、runST型の値を生成できなければなりません。そうするために、何らかの方法で. さらに、の実装がとして与えることを決定した型に関係なく、 type の値を生成できなければなりません。aaforall s. ST s aaarunSTs

したがって、実際には、このrunST関数は「私が typeaを選択できる限り、あなたは type を選択できます」と言っていますs

よし、それで?利点は、タイプがどのタイプになるかわからないため、タイプがタイプをまったく含むことができないrunSTという点で、これにより呼び出し元に制約が課されることです。たとえば、 type の値を渡すことはできません。これが実際に意味することは、 の実装は、型を含む値がそれ自体の実装に対してローカルであることを認識できるため、その場で変更するなど、他の方法では許可されないことを自由に実行できるということです。この型は、突然変異が の実装に対してローカルであることを保証します。assST s [s]runSTsrunST

の型は、引数の型に量指定子が含まれているため、ランク 2 の多相型runSTの例です。上記の型もランク 2 です。 のような通常の多相型はランク 1 ですが、引数の型が多相である必要があり、独自の量指定子がある場合はランク 2 になります。関数がランク 2 の引数を取る場合、その型はランク 3 などになります。一般に、rank のポリモーフィックな引数を取る型には rankがあります。forallfoobarforallnn + 1

于 2013-03-16T18:12:20.397 に答える
32

それらは、離散数学、圏論、または抽象代数の今週人気のある分野の最新のものを私が読んだという仮定がぎっしりと詰め込まれています。(「実装の詳細については論文を参照してください」という言葉を二度と読まなければ、早すぎます。)

ええと、単純な一次論理はどうですか? forallは明らかに全称量化を参照しており、その文脈では実存的existsという用語もより意味がありますが、キーワードがあればそれほど厄介ではありません. 量化が事実上普遍的であるか存在的であるかは、変数が関数矢印のどちら側で使用されているかに対する量指定子の配置に依存し、少し混乱します。

したがって、それが役に立たない場合、またはシンボリック ロジックが気に入らない場合は、より関数型のプログラミング的な観点から、型変数を関数の (暗黙的な)パラメーターであると考えることができます。この意味で型パラメーターを取る関数は、伝統的に、何らかの理由で大文字のラムダを使用して記述されています/\

したがって、次のid関数を検討してください。

id :: forall a. a -> a
id x = x

「型パラメーター」を型シグネチャから移動し、インライン型注釈を追加して、ラムダとして書き直すことができます。

id = /\a -> (\x -> x) :: a -> a

に対して行われた同じことは次のconstとおりです。

const = /\a b -> (\x y -> x) :: a -> b -> a

したがって、bar関数は次のようになります。

bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool)

に引数として与えられる関数の型は、の型パラメータbarに依存することに注意してください。bar代わりに次のようなものがあるかどうかを検討してください。

bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool)

ここでbar2は、関数を type のものに適用しているCharため、bar2以外の型パラメーターを指定Charすると型エラーが発生します。

一方、次のfooようになります。

foo = (\f -> (f Char 't', f Bool True))

とは異なりbarfoo実際には型パラメータをまったく取りません! それ自体が型パラメーターを取る関数を取り、その関数を 2 つの異なる型に適用します。

したがって、型シグネチャに a が表示された場合は、型シグネチャのラムダ式forallと考えてください。通常のラムダと同様に、のスコープは可能な限り右に、括弧を囲むまで拡張されます。また、通常のラムダでバインドされた変数と同様に、a でバインドされた型変数は、量化された式内でのみスコープ内にあります。forallforall


Post scriptum : おそらくあなたは疑問に思うかもしれません.型パラメーターを受け取る関数について考えているのに、それらのパラメーターを型シグネチャに入れるよりももっと面白いことをできないのはなぜですか? 答えは、できるということです。

型変数をラベルと組み合わせて新しい型を返す関数は型コンストラクターであり、次のように記述できます。

Either = /\a b -> ...

しかし、完全に新しい表記法が必要になります。なぜなら、そのような型の記述方法は、 のように、すでに「関数をこれらのパラメーターにEither a b適用する」ことを示唆しているためです。Either

一方、型パラメーターで一種の「パターン一致」を行い、異なる型に対して異なる値を返す関数は、型クラスのメソッドです/\上記の構文を少し拡張すると、次のようになります。

fmap = /\ f a b -> case f of
    Maybe -> (\g x -> case x of
        Just y -> Just b g y
        Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b
    [] -> (\g x -> case x of
        (y:ys) -> g y : fmap [] a b g ys 
        []     -> [] b) :: (a -> b) -> [a] -> [b]

個人的には、Haskell の実際の構文の方が好きだと思います...

型パラメーターに「パターンが一致」し、任意の既存の型を返す関数は、型ファミリまたは関数の依存関係です。前者の場合、すでに関数定義のように見えます。

于 2010-06-18T16:56:00.143 に答える
9

このキーワードの用途が異なる理由は、実際には少なくとも 2 つの異なる型システム拡張 (上位型と実存型) で使用されているためです。

「forall」が両方で同時に適切な構文である理由を説明しようとするのではなく、これら 2 つのことを別々に読んで理解することをお勧めします。

于 2010-06-18T17:26:12.980 に答える
4

実存的存在はどのように存在しますか?

Existential-Quantification では、定義forall内の s は、含まれる値がすべての適切な型である必要があるのではなく、任意の適切な型である可能性があることを意味します。--やちるの答えdata

forallin の定義が(疑似 Haskell)dataに同型である理由の説明は、ウィキブックの「Haskell/Existentially quantified types」にあります。(exists a. a)

以下は、簡単な逐語的な要約です。

data T = forall a. MkT a -- an existential datatype
MkT :: forall a. a -> T -- the type of the existential constructor

をパターンマッチング/分解するときMkT x、 の型はx何ですか?

foo (MkT x) = ... -- -- what is the type of x?

x( で説明されているように) 任意のタイプにすることができるforallため、そのタイプは次のとおりです。

x :: exists a. a -- (pseudo-Haskell)

したがって、以下は同形です。

data T = forall a. MkT a -- an existential datatype
data T = MkT (exists a. a) -- (pseudo-Haskell)

forall は forall を意味します

これらすべてについての私の単純な解釈は、「forall本当に「すべてのために」を意味する」ということです. 行うべき重要な違いはforall定義と関数の適用に対する の影響です。

Aforallは、値または関数の定義が多態的でなければならないことを意味します。

定義されているものがポリモーフィックな valueである場合、その値はすべての適切な に対して有効でなければならないことを意味しa、これは非常に制限的です。

定義されているものがポリモフィックな関数である場合、関数がすべての適切な関数に対して有効でなければならないことを意味します。関数がポリモフィックであるからといって、適用されるaパラメータがポリモフィックである必要があるとは限らないため、それほど制限的ではありません。つまり、関数がすべての に対して有効である場合、逆に適切な関数を関数に適用できます。ただし、パラメーターの型は、関数定義で 1 回しか選択できません。aa

aforallが関数パラメーターの型 (つまり a Rank2Type) 内にある場合、適用されるパラメーターは真に多態的でなければならないことを意味し、定義forallが多態的であることを意味するという考えと一致するようにします。この場合、パラメーターの型は、関数定義で複数回選択できます ( Norman が指摘したように、「関数の実装によって選択されます」 ) 。

したがって、存在data定義がany aを許可する理由は、データ コンストラクターが多相関数であるためです

MkT :: forall a. a -> T

MkTの種類::a -> *

これはa、関数に任意の値を適用できることを意味します。たとえば、ポリモーフィックな値とは対照的に:

valueT :: forall a. [a]

値の種類T ::a

つまり、valueTの定義は多態的でなければなりません。この場合、すべてのタイプのvalueT空のリストとして定義できます。[]

[] :: [t]

違い

for の意味はとforallで一貫していますが、コンストラクターはパターン マッチングで使用できるため、existentials には違いがあります。ghc ユーザー ガイドに記載されているとおり:ExistentialQuantificationRankNTypedata

パターン マッチングでは、パターン マッチごとに、存在型変数ごとに新しい個別の型が導入されます。これらの型は、他の型と統合することも、パターン マッチの範囲から逃れることもできません。

于 2015-02-06T18:49:31.840 に答える