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

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

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

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

Теперь я хочу определить новый экземпляр Ord для List таким образом, что List a

Прежде всего, необходимо ли определить новую функцию "sum", так как сумма, определенная в прелюдии, не будет работать с новым типом данных списка? затем, как я могу определить новый экземпляр Ord для списка?

Спасибо

5 4
haskell typeclass instances

5 ответов:

Во-первых, это не будет работать точно так же, как обычный экземпляр списка. Обычный экземпляр зависит только от того, что элементы списка сами упорядочиваются; ваше предложение зависит от того, что они являются числами (например, в классе 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. Эту функцию легко реализовать, поэтому я оставлю ее в качестве упражнения для читателя. (Я всегда хотел сказать, что: Р).
11

Как насчет...

newtype List a = List [a]

Это очень распространено, если вы хотите ввести новые," несовместимые " экземпляры класса типа для данного типа (см., например, ZipList или несколько моноидов, таких как Sum и Product)

Теперь вы можете легко повторно использовать экземпляры для списка, а также использовать sum.
4

Немного обобщая подход @ Tikhon, вы также можете использовать Monoid вместо Num в качестве ограничения, где у вас уже есть предопределенная "сумма" с mconcat (конечно, вам все еще нужен Ord). Это даст вам несколько больше типов в рассмотрение, чем просто числа (например, List (List a), которые теперь можно легко определить рекурсивно)

С другой стороны, если вы хотите использовать Num в качестве моноида, вы должны каждый раз решать для Sum или Product. Можно было бы возразить, что необходимость писать это явно может уменьшить краткость и читабельность, но это выбор дизайна, который зависит от того, какую степень обобщенности вы хотите иметь в конечном итоге.
2

О чем ..

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

Это то, что вы ищете?

0

.. или другое решение с функцией суммы в прелюдии.

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
0