如何創建一個可以引入新類型的Haskell函數？

我目前正在編寫一個表達式分析器。我已經完成了詞法和語法分析，現在我正在檢查類型。我有這樣的（簡體版）中的數據structire表達：如何創建一個可以引入新類型的Haskell函數？

data Expr = EBinaryOp String Expr Expr 
      | EInt Int 
      | EFloat Float

現在我需要這會將此轉換爲新類型的函數，說TypedExpr，這也將包含類型信息。現在我的主要問題是，這種類型應該是什麼樣子。我有兩個想法 - 用類型參數：

data TypedExpr t = TEBinaryOp (TBinaryOp a b t) (TExpr a) (TExpr b) 
       | TEConstant t 
addTypes :: (ExprType t) => Expr -> TypedExpr t

或不：

data TypedExpr = TEBinaryOp Type BinaryOp TypedExpr TypedExpr 
       | TEConstant Type Dynamic 
addTypes :: Expr -> TypedExpr

我開始了第一個選項，但我遇到了問題，因爲這種方法假定您知道表達的類型在解析它之前（對我來說，在大多數情況下都是如此，但並非總是如此）。但是，我喜歡它，因爲它允許我使用Haskell的類型系統，並在編譯時檢查大多數錯誤。

可以用第一個選項做到嗎？
你會選擇哪一個？爲什麼？
每個選項我應該期待什麼問題？

來源

2010-12-10 mik01aj

類型的功能

addTypes :: Expr -> TypedExpr t

是錯誤的，因爲這意味着你得到一個TypedExpr t爲你喜歡的任何t。相反，你實際上想要的是一個特定的t，它由Expr類型的參數確定。

這個推理已經表明你超越了Hindley-Milner類型系統的能力。畢竟，返回類型的addTypes應取決於值的參數，但在普通的Haskell 2010中，類型可能不依賴於值。因此，您需要擴展類型系統，使其更接近相關類型。在Haskell中，廣義代數數據類型（GADTs）可以做到這一點。

有關GADT的第一次介紹，另請參閱my video on GADTs。

但是，在熟悉GADT之後，仍然存在將無類型表達式解析爲類型化表達式的問題，即編寫一個函數

addTypes :: Expr -> (exists t. TypedExpr t)

當然，你必須執行某些類型檢查自己，但即使是這樣，這是不容易說服Haskell編譯你的類型檢查（這發生在價值層面），可以提升到類型級別。幸運的是，其他人已經想過這個問題，例如參見下面的消息在哈斯克爾咖啡廳的郵件列表：

愛德華Kmett。
回覆：手動類型檢查爲GADT提供讀取實例。（再次：哈斯克爾咖啡廳]閱讀實例GATD）
http://article.gmane.org/gmane.comp.lang.haskell.cafe/76466

（有誰知道的正式出版/寫得很好了參考？）

來源

2010-12-10 12:26:10

既然你做在運行時解析，而不是編譯的時候，你不能捎帶過Haskell的類型系統（除非您導入相關的模塊和手動調用它自己。）

您可能希望轉向TAPL的ML類型檢查器的例子，以獲得靈感的簡單lambda演算。（在實施中）。由於您不支持lambda表達式，因此它們會比表達式解析器做得更多。

來源

2010-12-10 11:18:18

我一直在使用tagless-final syntax最近開始了嵌入式DSL，我發現它比標準的GADT方法（你正朝着Apfelmus描述的方向）要好得多。

tagless-final語法的關鍵是不使用表達式數據類型，而是使用類型類表示操作。對於像您eBinaryOp功能，我發現它最好使用兩個類：

class Repr repr where 
    eInt :: repr Int 
    eFloat :: repr Float 

class Repr repr => BinaryOp repr a b c where 
    eBinaryOp :: String -> repr a -> repr b -> repr c

我會做單獨BinaryOp功能而非雖然使用字符串。關於Oleg's web page的更多信息，包括使用Haskell的類型系統的解析器。

來源

2010-12-10 15:23:08

哇！有趣的想法。永遠不會想到它:) – mik01aj 2010-12-10 17:02:55

我想我不明白你的解決方案太好 - eInt'，'eBinaryOp'應該做什麼？我在哪裏把我的'Expr'放在這個模型裏？ – mik01aj 2010-12-11 10:42:23

如何創建一個可以引入新類型的Haskell函數？

回答

相關問題