5

フォームのいくつかのステートメントを解析しています

v1 = expression1
v2 = expression2
...

私は State Monad を使用しており、私の状態は (String, Expr a) のペアである必要があります。GADT で PPair を定義する [PPair] として状態を実装しようとしました。

data PPair where
    PPair :: (String, Expr a) -> PPair

この行がコンパイラを通過すると、本当に間違ったことをしていると感じました。私はその考えを抑えて、コーディングを続けました。State から変数の値を抽出するコードを書き始めたとき、次の問題に気付きました。

evalVar k ((PPair (kk, v)):s) = if k == kk then v else evalVar k s

私は得る：

Inferred type is less polymorphic than expected

これはかなり期待されています。この問題を回避するにはどうすればよいですか? 型をすべての候補型 a に分割することで解決できることはわかっていますが、もっときちんとした方法はありませんか?

4

1 に答える 1

9

問題は、可能な型が存在しないことevalVarです:

evalVar :: String -> [PPair] -> Expr ?

?であるとは言えませんa。なぜなら、戻り値が の任意の値に対して機能すると主張しているためですa。ただし、できることは、「Expr未知の型を持つ an」を独自のデータ型にラップすることです。

data SomeExpr where
  SomeExpr :: Expr a -> SomeExpr

または、同等に、RankNTypesではなくGADTs:

data SomeExpr = forall a. SomeExpr (Expr a)

これは、存在量化と呼ばれます。PPair次に、次を使用して書き換えることができますSomeExpr。

data PPair = PPair String SomeExpr

そしてevalVarうまくいきます：

evalVar k (PPair kk v : xs)
  | k == kk = v
  | otherwise = evalVar k xs

(もちろん、[(String,SomeExpr)]代わりに a と標準lookup関数を使用することもできます。)

ただし、一般的に、このように式を完全に Haskell レベルで型付けしたままにしようとするのは、おそらく無駄なことです。Agdaのような依存型の言語では問題はありませんが、おそらく Haskell ではすぐに実行できない何かに遭遇したり、必要なコンパイル時の安全性が得られないところまで物事を弱体化させたりすることになるでしょう。失われます。

もちろん、決してうまくいかないというわけではありません。型付き言語は、GADT の動機となった例の 1 つです。しかし、それは思い通りにはいかないかもしれませんし、ポリモーフィズムのような自明ではない型システム機能が言語にある場合は、おそらく問題に遭遇するでしょう。

本当に入力を維持したい場合は、文字列よりも豊富な構造を使用して変数に名前を付けます。次のように、Var a型を明示的に運ぶ型を持っています。

data PPair where
  PPair :: Var a -> Expr a -> PPair

evalVar :: Var a -> [PPair] -> Maybe (Expr a)

これと同様のことを実現する良い方法は、vaultパッケージを使用することです。KeyとからSTを構築し、異種コンテナとしてIO使用できます。Vaultこれは基本的Mapに、キーが対応する値の型を保持する のようなものです。具体的には、Var aasを定義して、代わりにKey (Expr a)a を使用することをお勧めします。(完全な開示: 私は Vault パッケージに取り組んできました。)Vault[PPair]

もちろん、変数名をKey値にマップする必要がありますが、解析直後にすべての を作成しKey、文字列の代わりにそれらを持ち歩くことができます。(ただし、この戦略で a から対応する変数名に移動するのは少し手間Varがかかります。存在要素のリストを使用して実行できますが、解決策が長すぎてこの回答に入れることができません。)

(ちなみに、通常の型のように、GADT を使用してデータ コンストラクターに複数の引数を指定できますdata PPair where PPair :: String -> Expr a -> PPair。)

于 2012-01-20T17:36:01.510 に答える