帶類型的類型類型實例的類型參數約束* - > *

假設我有Heap a類型，其中Heap是種類* -> *的類型構造函數。堆上的許多基本操作要求a類型是Ord類型類的實例。帶類型的類型類型實例的類型參數約束* - > *

data Heap a = ... 

findMin :: Ord a => Heap a -> a 
deleteMin :: Ord a => Heap a -> Heap a

我想盡快a類型參數Ord類型的類的實例聲明我Heap類型Foldable型類的一個實例（它會很容易通過findMin和deleteMin函數來表示）。

這種關係可當我們需要的那種*類型類型類，處理像Show被easely表示：

instance Show a => Show (Heap a) where 
    show h = ...

但我有問題，與申報的Foldable：

instance Foldable Heap where 
    -- Ouch, there is no `a` type parameter to put the constraint on! 
    foldr f z h = ...

是否可以在這種實例聲明中對a類型參數設置約束？

來源

2012-09-19 roman-kashitsyn

看看[這個東西]（http://blog.omega-prime.co.uk/?p=127）。他們正在做一些與monads類似的事情。 – phg

非常感謝您的鏈接，'ConstraintKind'是_really_有趣的東西！ –

順便說一句，'findMin'真的需要一個'Ord'實例嗎？ – yairchu

一般來說，不，在給類型構造函數本身賦予實例時，沒有辦法約束它應用到的類型。大多數情況下這是一件好事，因爲它確保了例如Functor實例對於它們的元素類型是真正不可知的，這有助於保持良好和可預測的行爲良好且可預測。

有時這是一個煩惱，而最常見的例子確實需要一個Ord約束的排序數據結構，否則可能是一個不錯的，行爲良好的實例。

有一些涉及類似約束類的東西的實驗技術，但在您的具體情況下，已經有一個可行的解決方案。如果你看看Foldable的定義，它說只有foldMap或foldr需要實施，所以我們會考慮這些。注類型：

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b

在這兩種情況下，與Foldable實例的類型只出現一次，作爲參數傳遞給函數。正因爲如此，你可以use GADTs與Ord約束：

data Heap a where 
    Heap :: (Ord a) => ...

通過這樣做，你需要一個Ord比如你創建一個Heap值，即使是空堆的任何時間;但是當您的接收到 a Heap值時，其上的模式匹配將使Ord實例回到範圍內 - 即使在Foldable實例內！

請注意，這並不在許多其他情況下幫助：

fmap :: (Functor f) => (a -> b) -> f a -> f b

在這裏，我們可以a得到Ord實例，但我們也需要願意爲一個b，這是不可能的。

return :: (Monad m) => a -> m a

這裏我們還需要提供一個Ord實例。

來源

2012-09-19 16:41:22

謝謝，我知道它的工作原理，我準備了一個小樣本，在這裏如何做到這一點：http://ideone.com/HWl7H。對我來說這看起來很奇怪，但我們不能像這樣在類型聲明中使用約束：'newtype Ord a => ListHeap a = LH [a]'。這只是'可摺疊'實例不工作。我們確實必須使用模式匹配的GADT擴展。非常感謝您的回答！ –

@ roman-kashitsyn：是的，對於常規數據類型，有/是一種類似的語法，但它沒有做同樣的事情，並且是完全無用的錯誤特徵，最終可能會從語言標準中刪除（除非它已經當時我已經忘記了）。 –

看看在Hackage上的keys圖書館。檢查它的FoldableWithKey類型類是否是你需要的。

來源

2012-09-19 22:26:28 nponeccop

帶類型的類型類型實例的類型參數約束* - > *

回答

相關問題