創建列表

Question

新奧德實例這是我在創建類的自定義實例，如奧德第一次嘗試。

我已經定義了一個新的數據結構來表示一個列表：

data List a = Empty | Cons a (List a) 
    deriving (Show, Eq) 

現在我想ord定義的一個新實例列表，使得列表中< = B名單暗示「的總和列表a中的元素小於或等於列表b中元素的總和「

首先，是否有必要定義一個新的」總和「函數，因爲Prelude中定義的總和不會與新列表一起使用數據類型？那麼，我該如何定義Ord for List的新實例？

謝謝

Answer 1

首先，這不會像正常的列表實例一樣工作。正常實例僅取決於可自行訂購的列表項目;您的建議取決於他們是號（例如，在Num類）等是更窄。

有必要定義一個新的sum功能。令人高興的是，編寫sum作爲一個簡單的遞歸函數非常容易。 （巧合的是，你可以調用你的函數sum'，其發音爲「和總理」，並按照慣例意味着它非常類似於sum功能。）

此外，該實例將不得不依賴於Num類以及Ord類。

一旦你有一個新的sum功能，可以定義一個實例是這樣的：

instance (Ord n, Num n) => Ord (List n) where compare = ... 
    -- The definition uses sum' 

此實例語句可以理解爲說，爲各類n，如果n爲Ord和Num， List n在Ord中比較的工作如下。語法與暗含=>的數學非常相似。希望這會使記憶語法變得更容易。

你必須給的compare一個合理的定義。作爲參考，compare a b工作如下：如果a < b它返回LT，如果a = b它返回EQ，如果a > b它返回GT。

這是實現一個簡單的功能，所以我會離開它作爲一個練習給讀者。 （我一直想說：P）。

Answer 2

泛化@吉洪的做法了一下，你也可以使用Monoid代替Num爲約束，在那裏你已經有一個預定義的「總和」與mconcat（當然，你仍然需要Ord）。這會給你一些更多類型考慮的不僅僅是數字（如List (List a)，你現在可以輕鬆地遞歸定義）

在另一方面，如果你做要使用Num爲幺，你必須決定每次爲Sum或Product。有人可能會認爲，必須明確地寫出這些可以減少簡短性和可讀性，但這是一種設計選擇，最終取決於您希望達到的普遍程度。

Answer 3

......怎麼

newtype List a = List [a] 

這是如果要引入新的非常普遍，給定類型的「不兼容」類型的類實例（例如參見ZipList或幾個類羣像Sum和Product）

現在，您可以輕鬆地重新使用列表中的實例，並且還可以使用sum。

Answer 4

什麼..

data List a = Empty | Cons a (List a) 
       deriving (Show, Eq) 


instance (Ord a, Num a, Eq a) => Ord (List a) where 

     -- 2 empty lists 

     Empty <= Empty   = True 

     -- 1 empty list and 1 non-empty list 

     Cons a b <= Empty   = False 
     Empty <= Cons a b   = True 

     -- 2 non-empty lists 

     Cons a b <= Cons c d  = sumList (Cons a b) <= sumList (Cons c d) 


-- sum all numbers in list 

sumList   ::  (Num a) => List a -> a 

sumList Empty    =  0 
sumList (Cons n rest)  =  n + sumList rest 

這是你在找什麼？

Answer 5

..或另一個解決方案與和功能在Prelude。

data List a = Empty | Cons a (List a) 
       deriving (Show, Eq) 


instance (Ord a, Num a, Eq a) => Ord (List a) where 

     -- 2 empty lists 

     Empty <= Empty   = True 

     -- 1 empty list and 1 non-empty list 

     Cons a b <= Empty   = False 
     Empty <= Cons a b   = True 

     -- 2 non-empty lists 

     Cons a b <= Cons c d  = sum (listToList (Cons a b)) 
               <= sum (listToList (Cons c d)) 


-- convert new List to old one 

listToList  ::  (Num a) => List a -> [a] 

listToList Empty    =  [] 
listToList (Cons a rest)  =  [a] ++ listToList rest