打開和關閉開關類型遞歸

我正在研究一個簡單的編譯器。它從一個遞歸的複雜數據結構開始（即它是一個表達式樹），並以完全相同的數據結構結束，但不允許遞歸。打開和關閉開關類型遞歸

「沒問題」，我想我自己，「我只是讓遞歸類型成爲一個類型參數，然後爲遞歸和非遞歸類型定義類型同義詞」。

......嗯，是的，但事實證明，你不能這樣做。你看，類型同義詞不允許遞歸。 > facepalm <

任何想法如何我可以實現我後？

下面是一個非常簡單的例子。假設我有這兩個數據類型：

data Type1 = Foo ID | Bar [Type1] | Baz Type1 Type1 

data Type2 = Foo ID | Bar [ID] | Baz ID ID

我的計劃是簡單地做到這一點：

data Type r = Foo ID | Bar [r] | Baz r r 

type Type1 = Type Type1 
type Type2 = Type ID

但顯然這並不實際工作。

目前，看來我的選擇是這些：

忽略的問題，不要試圖在一個類型系統來強制實施此限制。
複製整個類型定義（包括重命名所有構造函數）。

這些都不是真的令人滿意。對於上面這個簡單的例子，複製類型並不算太壞;對於大類型定義，你不想這樣做！

來源

2014-07-26 MathematicalOrchid

你可以這樣做：

data Type r = Foo ID | Bar [r] | Baz r r 

newtype Type1 = Type1 (Type Type1) 
newtype Type2 = Type2 (Type ID) -- or type Type2 = Type ID, but this is more consistent

您需要刪除處理Type1功能的額外的類型構造，但是這不應該是一個大問題。

更一般地，您可以定義a fixed-point type constructor並將其用於定義Type1。

來源

2014-07-26 12:11:57

我曾希望避免數百個包裝和解包操作，但似乎沒有其他辦法。：-S – MathematicalOrchid

@MathematicalOrchid：我會使用模式同義詞來幫助解決這個問題。 –

這聽起來像你可能使用recursion-schemes。你基本上有兩種選擇：

使用Fix（或Mu或Nu）創建遞歸變種，這意味着包裝它的構造所有的時間有些滋擾與（聯合國）。
```
data TypeF r = FooF ID | BarF [r] | BazF r r 
    deriving (Functor) 

type Type1 = Fix TypeF 
type Type2 = TypeF ID 
```

定義你自己的變型的遞歸情況，並根據需要實施project/embed：

data Type = Foo ID | Bar [Type] | Baz Type Type 

type instance Base Type = TypeF 

instance Foldable Type where 
    project (Foo ID) = FooF ID 
    project (Bar xs) = BarF xs 
    project (Baz x y) = BazF x y 

instance Unfoldable Type where 
    embed (FooF ID) = Foo ID 
    embed (BarF xs) = Bar xs 
    embed (BazF x y) = Baz x y

類型家庭Base提供了兩者之間的聯繫：project和embed見證Type之間的同構和Base Type Type和Base Type Type相當於TypeF Type，展開一個遞歸級別。

在這兩種情況下Foldable和落實各項* -morphisms的遞歸和非遞歸表示之間轉換。

來源

2014-07-26 13:49:31

打開和關閉開關類型遞歸

回答

相關問題