理解和使用 Haskell 的 Integral 类型类的基本概念

Question

我正在学习一门侧重于 Haskell 和 Prolog 的课程，并且我正在学习即将进行的测试。

我们得到了签名：

myList
  :: (Integral a)
  => [a]

并且我们必须创建一个变量 myList 它将 return 一个无限列表，它不同于标准的正整数列表，通过将每个第三个元素移动两个位置到对了，从第一个开始。

例如，开头看起来像： 2,3,1,5,6,4,8,9,7.. 在包含正元素的标准列表上。

我试图用这样的代码解决这个问题：

myList (x:y:z:xs)
  = y:z:x:(myList(xs))
myList [] = []
myList [x] = [x]

它给出了所需的结果，但没有遵循签名。有人可以解释如何解决它以使其适合签名以及为什么会这样。

谢谢。

Answer 1

函数（事实上你完全正确的实现）

myList (x:y:z:xs) = y:z:x:(myList xs)
myList []         = []
myList [x]        = [x]

足够通用，不依赖于列表中元素的类型 Integral a => a。所以如果你让 Haskell 推断它的类型，它会推断 [a] -> [a]。如果您将类型限制为 Integral a => [a] -> [a]，它仍然可以工作，但不太通用，这将限制使用整数类型。

原理演示如下：

Prelude> :{
Prelude| let myList (x:y:z:xs) = y:z:x:(myList(xs))
Prelude|     myList [] = []
Prelude|     myList [x] = [x]
Prelude| :}
Prelude> :t myList
myList :: [a] -> [a]

Prelude> take 15 $ myList ['a'..]
"bcaefdhigkljnom"
Prelude> take 15 $ myList [1..]
[2,3,1,5,6,4,8,9,7,11,12,10,14,15,13]

但是

Prelude> :{
Prelude| let myList :: Integral a => [a] -> [a]
Prelude|     myList (x:y:z:xs) = y:z:x:(myList(xs))
Prelude|     myList [] = []
Prelude|     myList [x] = [x]
Prelude| :}
Prelude> :t myList
myList :: Integral a => [a] -> [a]

Prelude> take 15 $ myList [1..]
[2,3,1,5,6,4,8,9,7,11,12,10,14,15,13]

Prelude> take 15 $ myList ['a'..]    
<interactive>:34:11:
    No instance for (Integral Char) arising from a use of ‘myList’
    In the second argument of ‘($)’, namely ‘myList ['a' .. ]’
    In the expression: take 15 $ myList ['a' .. ]
    In an equation for ‘it’: it = take 15 $ myList ['a' .. ]

所以重点是，这两个定义是等价的，并且能够像另一个一样做同样的事情，但是受约束的类型签名是（我会说不合理的）不如具有通用类型签名的有用。

如果赋值需要一个类型为 Integral a => [a] -> [a] 的函数，您真正需要做的只是简单地使用该类型签名来注释您已有的函数。但是，没有 (reasonable/rational) 方法以某种方式引导 Haskell 从函数定义中推断出该类型，因为这将需要以某种方式间接指示列表必须包含支持该类型的值Integral 中的操作 ... yada yada.

最后一点：您的 implementation/algorithm 完全正确，但在类型签名和通用性概念方面有所欠缺。

编辑： 如果你真正需要的不是一个函数而是一个列表（你的问题在这方面有点含糊），你需要做的就是重命名下面的myList 的定义例如myList' 或 go（我认为这是嵌套递归助手的典型名称）或其他名称（可以但不必隐藏在列表 myList 中）然后将 [1..] 传递给它，将结果分配给 myList:

myList :: Integral a => [a]
myList = go [1..]
  where go (x:y:z:xs) = y:z:x:(go xs)
        go []         = []
        go [x]        = [x]

当然是这样看的，Integral a => [a] 是确实是一个很一般的列表签名（但不是最一般的，应该是(Enum a, Num a) => [a]正如 dfeuer 的评论让我意识到的那样），因为类型 a 不能由传递给函数的输入类型确定，因为你总是传递 [1..].

Answer 2

如果我们想用正确的签名给出答案 而无需 手动提供任何签名，我们必须查看 Integral class 并查看它的方法实施。应用任何此类方法都可能强制使用正确的签名。

Prelude> :i Integral
class (Real a, Enum a) => Integral a where
  quot :: a -> a -> a
  rem :: a -> a -> a
  div :: a -> a -> a
  mod :: a -> a -> a
  quotRem :: a -> a -> (a, a)
  divMod :: a -> a -> (a, a)
  toInteger :: a -> Integer

由于我们的序列与除以 3 的余数有关，div 和 mod 看起来很有希望。

经过一些算术运算，我们得到了类似

的结果

Prelude> let myList = map (\x -> x - x `mod` 3 + (x+2) `mod` 3 + 1) [0..]
Prelude> :t myList
myList :: Integral b => [b]

理解和使用 Haskell 的 Integral 类型类的基本概念

Understand and use the basic concept of Haskell's Integral typeclass

haskell

types

typeclass