5

関数の適用を表す型付き抽象構文ツリー データ型を作成しようとしています。

これまでのところ、

type Expr<'a> =
    | Constant    of 'a
    | Application of Expr<'b -> 'a> * Expr<'b> // error: The type parameter 'b' is not defined

F# で最後の行に 'for all b' のようなものを書く方法はないと思います - この問題に間違ってアプローチしていますか?

4

1 に答える 1

10

一般に、F＃型システムは、型付きの抽象構文ツリーを例のように（直接）定義するのに十分な表現力を備えていません。これは、F＃ではサポートされていない一般化代数的データ型（GADT）を使用して実行できます（ただし、HaskellとOCamlでは使用できます）。これをF＃で使用すると便利ですが、言語が少し複雑になると思います。

技術的に言えば、型変数'bが定義されていないため、コンパイラは文句を言っています。しかしもちろん、それを定義すると、Expr<'a, 'b>異なる意味を持つ型が得られます。

これをF＃で表現したい場合は、インターフェイスに基づく回避策を使用する必要があります（インターフェイスには、exists 'bここで必要なような制約を表現する方法を提供するジェネリックメソッドを使用できます）。これはおそらくすぐに非常に醜くなるので、良いアプローチではないと思いますが、次のようになります。

// Represents an application that returns 'a but consists
// of an argument 'b and a function 'b -> 'a
type IApplication<'a> =
  abstract Appl<'b> : Expr<'b -> 'a> * Expr<'b> -> unit

and Expr<'a> = 
  // Constant just stores a value...
  | Constant    of 'a 
  // An application is something that we can call with an 
  // implementation (handler). The function then calls the
  // 'Appl' method of the handler we provide. As this method
  // is generic, it will be called with an appropriate type
  // argument 'b that represents the type of the argument.
  | Application of (IApplication<'a> -> unit)

の式ツリーを表すには(fun (n:int) -> string n) 42、次のように記述します。

let expr = 
  Application(fun appl -> 
    appl.Appl(Constant(fun (n:int) -> string n), 
              Constant(42)))

式を評価する関数は、次のように記述できます。

let rec eval<'T> : Expr<'T> -> 'T = function
  | Constant(v) -> v   // Just return the constant
  | Application(f) ->
      // We use a bit of dirty mutable state (to keep types simpler for now)
      let res = ref None
      // Call the function with a 'handler' that evaluates function application
      f { new IApplication<'T> with
            member x.Appl<'A>(efunc : Expr<'A -> 'T>, earg : Expr<'A>) = 
              // Here we get function 'efunc' and argument 'earg'
              // The type 'A is the type of the argument (which can be
              // anything, depending on the created AST)
              let f = eval<'A -> 'T> efunc
              let a = eval<'A> earg
              res := Some <| (f a) }
      res.Value.Value

私が言ったように、これは少し本当に極端な回避策なので、実際に使用するのは良い考えではないと思います。これを行うF＃の方法は、型指定されていないExpr型を使用することだと思います。プロジェクトの全体的な目標についてもう少し詳しく教えていただけますか（おそらく別の良いアプローチがあります）？

于 2012-09-23T14:02:43.773 に答える