數據類型定義的限制

Question

對於Feature和Body的意思，我有一個類型的同義詞type Entity = ([Feature], Body)。 Entity類型的對象是組合在一起：

type Bunch = [Entity] 

和假設，對於算法Bunch工作的關鍵，是在同一羣任何兩個實體的功能同等數量。

如果我要在OOP語言中實現這個約束，我會將相應的檢查添加到封裝添加實體的方法中。 在Haskell中有更好的方法嗎？優選地，在定義級別上。 （如果Entity的定義也需要改變，沒問題。）

Answer 1

使用類型級長度標註

所以這裏的交易。 Haskell確實有type-level natural numbers，您可以使用「幻像類型」對類型進行註釋。但是你這樣做，該類型將是這樣的：

data Z 
data S n 
data LAList x len = LAList [x] -- length-annotated list 

然後你就可以添加一些功能建設爲方便：

lalist1 :: x -> LAList x (S Z) 
lalist1 x = LAList [x] 
lalist2 :: x -> x -> LAList x (S (S Z)) 
lalist2 x y = LAList [x, y] 
-- ... 

然後你已經有了比較通用的方法：

(~:) :: x -> LAList x n -> LAList x (S n) 
x ~: LAList xs = LAList (x : xs) 
infixr 5 ~: 

nil :: LAList x Z 
nil = LAList [] 

lahead :: LAList x (S n) -> x 
lahead (LAList xs) = head xs 

latail :: LAList x (S n) -> LAList x n 
latail (LAList xs) = tail xs 

但本身列表定義沒有任何這個，因爲它很複雜。您也許對Data.FixedList軟件包感興趣，但也有一些不同的方法。基本上，每種方法都會從一些沒有構造函數的數據類型開始看起來有點奇怪，但稍微有點後就開始看起來很正常。

您可能也能夠得到一個類型類讓所有的lalist1的，lalist2運營商上面可以用

class FixedLength t where 
    la :: t x -> LAList x n 

替換，但你可能會需要-XTypeSynonymInstances標誌要做到這一點，因爲你要像做

type Pair x = (x, x) 
instance FixedLength Pair where 
    la :: Pair x -> LAList [x] (S (S Z)) 
    la (a, b) = LAList [a, b] 

（它是一種不匹配時，你去從(a, b)到Pair a）。

使用運行時檢查

你可以很容易地採取不同的方法和封裝所有的這是一個運行時錯誤或直接在您的代碼中的錯誤模式：

-- this may change if you change your definition of the Bunch type 
features :: Entity -> [Feature] 
features = fst 

-- we also assume a runBunch :: [Entity] -> Something function 
-- that you're trying to run on this Bunch. 

allTheSame :: (Eq x) => [x] -> Bool 
allTheSame (x : xs) = all (x ==) xs 
allTheSame [] = True 

permissiveBunch :: [Entity] -> Maybe Something 
permissiveBunch es 
    | allTheSame (map (length . features) es) = Just (runBunch es) 
    | otherwise = Nothing 

strictBunch :: [Entity] -> Something 
strictBunch es 
    | allTheSame (map (length . features) es) = runBunch es 
    | otherwise = error ("runBunch requires all feature lists to be the same length; saw instead " ++ show (map (length . features) es)) 

那麼你runBunch可以只是假設所有的長度都是相同的，並且明確地檢查了上面的內容。如果需要將特徵彼此相鄰配對，則可以利用Prelude中的zip :: [a] -> [b] -> [(a, b)]函數解決模式匹配的奇怪問題。 （這裏的目標是由於runBunch' (x:xs) (y:ys)和runBunch' [] []的模式匹配而導致的算法錯誤，但是Haskell警告說有兩種模式在比賽中沒有考慮到。）

使用元組和類型類

最後一個辦法做到這一點這是兩者之間的妥協（但做了相當不錯的Haskell代碼）包括使實體參數化了對所有功能：

type Entity x = (x, Body) 

然後包括它可以壓縮不同長度的不同實體在一起的功能：

class ZippableFeatures z where 
    fzip :: z -> z -> [(Feature, Feature)] 

instance ZippableFeatures() where 
    fzip()() = [] 

instance ZippableFeatures Feature where 
    fzip f1 f2 = [(f1, f2)] 

instance ZippableFeatures (Feature, Feature) where 
    fzip (a1, a2) (b1, b2) = [(a1, b1), (a2, b2)] 

然後你可以使用元組的功能列表，只要它們不超過最大元組長度（這是我的GHC上的15）。如果你比這更大，當然，你總是可以定義自己的數據類型，但它不會像類型註釋列表一樣普遍。

如果你這樣做，對你的runBunch類型簽名會簡單地樣子：

runBunch :: (ZippableFeatures z) => [Entity z] -> Something 

當你對事物有錯號碼的功能，你會得到編譯器錯誤，它不能統一運行（a，b，c）的類型（a，b）。

Answer 2

有多種方式來強制這樣的長度約束;這裏有一個：

{-# LANGUAGE DataKinds, KindSignatures, GADTs, TypeFamilies #-} 
import Prelude hiding (foldr) 
import Data.Foldable 
import Data.Monoid 
import Data.Traversable 
import Control.Applicative 

data Feature -- Whatever that really is 

data Body -- Whatever that really is 

data Nat = Z | S Nat -- Natural numbers 

type family Plus (m::Nat) (n::Nat) where -- Type level natural number addition 
    Plus Z n = n 
    Plus (S m) n = S (Plus m n) 

data LList (n :: Nat) a where -- Lists tagged with their length at the type level 
    Nil :: LList Z a 
    Cons :: a -> LList n a -> LList (S n) a 

這些列表中的一些功能：

llHead :: LList (S n) a -> a 
llHead (Cons x _) = x 

llTail :: LList (S n) a -> LList n a 
llTail (Cons _ xs) = xs 

llAppend :: LList m a -> LList n a -> LList (Plus m n) a 
llAppend Nil ys = ys 
llAppend (Cons x xs) ys = Cons x (llAppend xs ys) 

data Entity n = Entity (LList n Feature) Body 

data Bunch where 
    Bunch :: [Entity n] -> Bunch 

一些實例：

instance Functor (LList n) where 
    fmap f Nil = Nil 
    fmap f (Cons x xs) = Cons (f x) (fmap f xs) 

instance Foldable (LList n) where 
    foldMap f Nil = mempty 
    foldMap f (Cons x xs) = f x `mappend` foldMap f xs 

instance Traversable (LList n) where 
    traverse f Nil = pure Nil 
    traverse f (Cons x xs) = Cons <$> f x <*> traverse f xs 

等。請注意，n中的Bunch的定義是存在。它可以是任何東西，它實際上並不影響類型 - 所有串都具有相同的類型。這在一定程度上限制了你可以用束做什麼。或者，您可以使用其功能列表的長度來標記該組。這一切都取決於你需要什麼做這個東西到底。