haskell中的類型級多態性

我正在通過Richard Bird和Ross Paterson的論文De bruijn notation as a nested datatype。在一個一個點上的一個術語摺疊操作被定義爲：haskell中的類型級多態性

infixl 9 :@ 

data Expr a = 
     Var a 
    | (Expr a) :@ (Expr a) 
    | Lam (Expr (Maybe a) 

foldT :: 
    (forall a. a -> n a) -> 
    (forall a. n a -> n a -> n a) -> 
    (forall a. n (Maybe a) -> n a) -> 
    Expr b -> n b 
foldT v _ _ (Var x) = v x 
foldT v a l (fun :@ arg) = a (foldT v a l fun) (foldT v a l arg) 
foldT v a l (Lam body) = l (foldT v a l body)

...並進一步爲通用版本，允許自由瓦爾值的操作：

gfoldT :: 
    (forall a. m a -> n a) -> 
    (forall a. n a -> n a -> n a) -> 
    (forall a. n (Maybe a) -> n a) -> 
    (forall a. (Maybe (m a)) -> m (Maybe a)) ->  
    Expr (m b) -> n b        
gfoldT v _ _ _ (Var x) = v x 
gfoldT v a l t (fun :@ arg) = a (gfoldT v a l t fun) (gfoldT v a l t arg) 
gfoldT v a l t (Lam body) = l (gfoldT v a l t (mapT t body))

然後，作者狀態：

從理論上講，我們可以採取m = id，身份類型構造，並因此獲得foldT v a l = gfoldT v a l id。（...）但是，類型 haskell中的構造函數多態性是有限的，在該類型中構造函數變量可能只能實例化爲數據類型構造函數。

而且他們進一步表示，爲此，我們需要一次性的專門功能，如上面的foldT。

我想知道究竟是什麼type constructor polymorphism意味着在這方面（類似全System F？），如果像foldT v a l = gfoldT v a l id可以通過新增加的類型層次的編程功能的手段像 DataKinds，PolyKinds或TypeFamilies來實現。

來源

2016-03-09 jules

引用源時，使用* actual *引用塊，而不是斜體。語義結構可以被例如盲人屏幕閱讀器利用，以更好地呈現該問題。 – Bakuriu

@Bakuriu，屏幕閱讀器不會識別雙引號嗎？我同意引用塊對於這樣長的東西肯定是可取的，但我很好奇。 – dfeuer

@Bakuriu，謝謝你的提示！ – jules

我認爲這句話指的是缺乏類型級的lambda抽象。具體而言，以下是非法的，在Haskell中。

data T m a = T (m a) 

foo :: T (\t -> t) Int 
foo = T 5

有人可能試圖用類型同義詞或類型族來規避問題，但沒有成功。以下是不允許的：

type F t = t 
foo :: T F Int 
foo = T 5

既不是這樣的：

type family F a 
type instance F a = a 
foo :: T F Int 
foo = T 5

在Haskell，類型方程m Int ~ Int無解：m必須是一個數據類型構造函數。事實上，編譯器依賴於統一時的內射，這很容易被任意的類型級函數所侵犯。

一個可以然而使用m ~ Identity和獲得Identity Int其是從Int不同，但同構。

目前，我認爲safe coercions功能不夠強大，使用Identity Int將類型強制轉換爲直接使用Int的類似類型。因此，Identity包裝必須手動刪除，以獲得更簡單的摺疊類型。

來源

2016-03-09 16:52:25 chi

（或者一個類型的構造函數或類適用於一個或多個參數，我傾向於調用所有這些「頭等類型」，但我不知道官方術語）。安全強制有時足夠，但通常不會。 – dfeuer

haskell中的類型級多態性

回答

相關問題