Создание нового экземпляра Ord для списков

Question

Это моя первая попытка создать собственный экземпляр класса, такого как Ord.

Я определил новую структуру данных для представления списка:

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

Теперь я хочу, чтобы определить новый экземпляр Ord для списка таким образом, что Сдать < = Список б означает «сумму из элементы в списке a меньше или равны сумме элементов в списке b «

Прежде всего, необходимо определить новую функцию« sum », так как сумма, определенная в Prelude, не будет работать с новым списком тип данных? то как я могу определить новый экземпляр Ord для 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

.. или другое решение с функцией sum в 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