関数アプリケーション付きの型付き抽象構文ツリー

Question

関数アプリケーションを表すことができる型付き抽象構文ツリーのデータ型を記述しようとしています。

これまでのところ、私は

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

を持って、私はその最後の行に「すべてのBの」のような何かを書くためのF＃での方法があるとは思わない - 私は間違ってこの問題に近づいていますか？

Answer 1

一般に、F＃タイプのシステムは、型付きの抽象構文ツリーを例のように（直接的に）定義するのに十分ではありません。これは、F＃でサポートされていないgeneralized algebraic data types (GADTs)を使って行うことができます（HaskellとOCamlで利用可能ですが）。 F＃でこれを使用するといいですが、言語が少し複雑になると思います。

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

これをF＃で表現したいのであれば、インターフェイスに基づく回避策を使用する必要があります（インターフェイスには一般的な方法がありますので、ここに必要なexists 'bのような制約を表現できます）。これはおそらく、非常にすぐに非常に醜い取得しますので、私はそれが良いアプローチだとは思わないが、それはこのようなものになります。(fun (n:int) -> string n) 42の式ツリーを表現するために

// 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) 

を、あなたのような何かを書くことができます：

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タイプを使用することになると思います。プロジェクトの全体的な目標についてもう少し詳しく書くことができますか（別の良いアプローチがあるかもしれません）？