5

这是我第一次尝试创建 Ord 等类的自定义实例。

我定义了一个新的数据结构来表示一个列表：

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

现在我想为 List 定义一个新的 Ord 实例，使得 List a <= List b 意味着“List a 中元素的总和小于或等于 List b 中元素的总和”

首先，是否有必要定义一个新的“sum”函数，因为 Prelude 中定义的 sum 不适用于新的 List 数据类型？那么，如何为 List 定义新的 Ord 实例？

谢谢

4

5 回答 5

13

首先，这不会像普通的列表实例一样工作。普通实例仅取决于列表中的项目本身是可订购的；您的建议取决于他们的数量（例如在Num课堂上），因此更狭窄。

有必要定义一个新sum函数。令人高兴的是，它很容易编写sum为一个简单的递归函数。（巧合的是，你可以调用你的函数sum'，它的发音是“sum prime”，按照惯例，它是一个与 非常相似的函数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比较工作的地方如下。语法非常类似于数学 where =>is implying。希望这能让记忆语法更容易。

你必须给出一个合理的定义compare。作为参考，compare a b工作原理如下：如果a < b它返回LT，如果a = b它返回EQ，如果a > b它返回GT。

这是一个易于实现的功能，因此我将把它作为练习留给读者。（我一直想说：P）。

于 2012-05-25T04:51:02.860 回答
4

怎么样...

newtype List a = List [a]

如果您想为给定类型引入新的“不兼容”类型类实例，这很常见（参见 egZipList或几个像Sumand之类的 monoid Product）

现在您可以轻松地重用列表的实例，并且您也可以使用sum。

于 2012-05-25T07:16:51.960 回答
2

稍微概括@Tikhon的方法，您也可以使用Monoid而不是Num作为约束，您已经有一个预定义的“总和” mconcat（当然，您仍然需要Ord）。这将使您考虑更多类型，而不仅仅是数字（例如List (List a)，您现在可以轻松地递归定义）

另一方面，如果你确实想使用 aNum作为幺半群，你必须每次都决定 for Sumor Product。可以说，必须明确地写出来会降低简短性和可读性，但这是一种设计选择，取决于您最终希望拥有何种程度的通用性。

于 2012-05-25T05:46:52.143 回答
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      =   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

这是你想要的？

于 2012-05-25T14:19:47.670 回答
0

.. 或 Prelude 中具有 sum 函数的其他解决方案。

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
于 2012-05-25T14:54:36.840 回答