2016-11-13 18 views
2

我目前正在嘗試構建一個lambda微積分求解器,並且在構建AST時遇到了一些小問題。甲演算術語感應定義爲:Haskell AST與遞歸類型

1)一種可變

2)的λ,變量,一個點,一個lambda表達式。

3)括號,lambda表達式,lambda表達式和括號。

我想怎麼做(在第一次嘗試)是這樣的:

data Expr = 
    Variable 
    | Abstract Variable Expr 
    | Application Expr Expr 

現在很明顯這是行不通的,因爲變量是不是一個類型的,和抽象變Expr的期望類型。所以,我的哈克解決方案,這是有:

type Variable = String 

data Expr = 
    Atomic Variable 
    | Abstract Variable Expr 
    | Application Expr Expr 

現在,這實在是煩人,因爲我不喜歡自己的原子變量,但摘要採取字符串,而不是EXPR。有什麼辦法可以讓這個更優雅,並且像第一個解決方案那樣做?

+0

您發現令人厭惡的第二個定義是執行此操作的標準方法。我的建議是,習慣它。你的思維方式與Haskell的類型系統不兼容,所以請繼續並訓練自己。 – luqui

回答

3

你的第一個解決方案只是一個沒有意義的錯誤定義。 Variable不是那裏的一個類型,它是一個空值構造函數。您不能在類型定義中引用Variable,就像您不能引用任何值一樣,如True,False100

第二種解決方案是實際上的東西,我們可以在BNF編寫直接翻譯:

var ::= <string> 
term ::= λ <var>. <term> | <term> <term> | <var> 

因而存在不妥的地方。

1

你到底想要的是有某種類型的像

data Expr 
    = Atomic Variable 
    | Abstract Expr Expr 
    | Application Expr Expr 

但是限制第一ExprAbstract構造是唯一Atomic。在Haskell中沒有直接的方法可以做到這一點,因爲某些類型的值可以由任何這種類型的構造函數創建。因此,唯一的方法是爲現有類型創建一些單獨的數據類型或類型別名(例如Variable類型別名)並將所有通用邏輯移入其中。你的解決方案與Variable似乎對我很好。

但是。您可以使用Haskell中的其他一些高級功能以不同的方式實現您的目標。您可以從glambda包中獲得靈感,它使用GADT來創建類型化的lambda演算。也看到這個答案:https://stackoverflow.com/a/39931015/2900502

我能拿出一個解決方案,以實現您的最小目標(如果你只是想約束的Abstract第一個參數):

{-# LANGUAGE GADTs   #-} 
{-# LANGUAGE KindSignatures #-} 

data AtomicT 
data AbstractT 
data ApplicationT 

data Expr :: * -> * where 
    Atomic  :: String -> Expr AtomicT 
    Abstract :: Expr AtomicT -> Expr a -> Expr AbstractT 
    Application :: Expr a -> Expr b -> Expr ApplicationT 

而下面的例子正常工作:

ex1 :: Expr AbstractT 
ex1 = Abstract (Atomic "x") (Atomic "x") 

但由於類型不匹配的這個例子不會編譯:

ex2 :: Expr AbstractT 
ex2 = Abstract ex1 ex1 
+0

不夠公平,如果我做一個函數來檢查(Abstract Expr Expr)的每個實例只有一個原子值作爲第一個Expr,expr解決方案可能就足夠了。想想我會在我的問題中採用第二種解決方案,因爲它似乎是最受歡迎的。 – user2850249

+0

@ user2850249你可能沒有看到我的下半部分答案。如果您使用'GADT',則不需要創建函數來檢查每個「Abstract Expr Expr」是否具有原子值作爲第一個'Expr'。如果你使用非原子作爲第一個'Expr',你的代碼就不會編譯。並且在運行時保證你的第一個'Expr'永遠是'Atomic'。 – Shersh