F＃表達式樹解釋器的實現

Question

我試圖構建一個可以在F＃中添加或乘法的表達式樹的解釋器，但是我遇到了一些麻煩。我還試圖使用選項類型，以便解釋器在該表達式中不包含變量時返回None。

這是我給的代碼。

type Exptree = 
    | Const of int 
    | Var of string 
    | Add of Exptree * Exptree 
    | Mul of Exptree * Exptree 

type Bindings = (string * int) list 

let rec eval(exp : Exptree, env:Bindings) = 
    match exp with 
    | 

我很困惑與exp匹配的是什麼，因爲有這麼多選項。我的想法是查看Add和Mul，並嘗試在每個遞歸步驟中刪除它，直到我得到一個整數，但是我完全失去了。

我可以做類似的事嗎？

match exp with 
| Some(Add) -> int + int? 
| Some(Mul) -> int * int? 

Answer 1

您的Exptree類型有四種可能的構造函數：Const，Var，Add和Mul。所以，你的對手將是對那些：

match exp with 
| Const c -> 
| Var s -> 
| Add (e1,e2) -> 
| Mul (e1,e2) -> 

對於每一個這種情況下，你會做相應的操作（加法，乘法，查找環境變量，返回一個常數）。在add和mul的情況下，你會解釋eval在子表達式（e1和e2）上遞歸調用的結果，看看該值是None還是Some（s），並相應地作用於它。

Answer 2

因此，scrwtp是正確的，Map<string, int>對於您的一組綁定更有意義，因爲您可以在O（log n）時間內執行查找，而不是使用list進行O（n）時間查找。

的eval功能的第一部分很簡單：

1. 如果該值是恆定的，我們只需要返回不變的Some。
2. 如果該值是一個變量，我們需要在地圖上查找它，如果該鍵存在，我們返回值爲Some。如果他們的鑰匙不存在，我們將返回None。我們可以使用Map.tryFind來做到這一點。

我們能做到這一點的部分是這樣的：

let rec eval bindings tree = 
    match tree with 
    |Const i -> Some i 
    |Var varName -> Map.tryFind varName bindings 

執行加法和乘法需要一些更多的思考。爲了抽象地合併兩個子樹，定義一個函數將兩個選項作爲參數是有意義的，並且如果它們都是Some value，則可以將函數應用於兩個結果。這就是所謂的lift2功能，我們可以將其定義爲Option：

/// Combines two option values using a supplied function 
let lift2 f opt1 opt2 = 
    match (opt1, opt2) with 
    |Some val1, Some val2 -> Some <| f val1 val2 
    |_ -> None 

欲瞭解更多的lift家庭的功能，看到這個偉大的教程：http://fsharpforfunandprofit.com/posts/elevated-world/#lift

現在我們可以擴展我們eval功能的加法並通過調用這個函數來乘法情況。現在

/// Evaluates the result of an expression tree 
let rec eval bindings tree = 
    match tree with 
    |Const i -> Some i // Const always returns some value 
    |Var varName -> Map.tryFind varName bindings // Returns some value if it exists in the binding table 
    |Add (tree1, tree2) -> 
     lift2 (+) (eval bindings tree1) (eval bindings tree2) // add expressions if both expressions return Some val 
    |Mul (tree1, tree2) -> 
     lift2 (*) (eval bindings tree1) (eval bindings tree2) // multiply expressions if both expressions return Some val 

，添加的情況下使用lift2功能地說，如果兩個子表達式計算爲一個真正的價值，結果加在一起，否則返回None。

乘法情況遵循完全相同的邏輯，我們只是交換操作符。

快速旁白：作爲GuyCoder指出，建立自己的綁定表的便捷方式將被使用的語法：

let bindings = Map.ofList [("a",1); ("b",2); ("c",3)]