Haskell AST與遞歸類型

我目前正在嘗試構建一個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。有什麼辦法可以讓這個更優雅，並且像第一個解決方案那樣做？

來源

2016-11-13 user2850249

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

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

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

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

因而存在不妥的地方。

來源

2016-11-13 10:12:47

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

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

但是限制第一Expr在Abstract構造是唯一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

來源

2016-11-13 10:28:35 Shersh

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

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

Haskell AST與遞歸類型

回答

相關問題