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

Question

我正在学习一门专注于Haskell和Prolog的课程,我正在研究即将进行的测试.

我们给了签名:

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

我们必须创建一个变量myList,它将返回一个与标准正整数列表不同的无限列表,方法是从第一个元素开始向右移动两个位置来改变每个第三个元素的位置.

因此,例如,开头看起来像: 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],那么您真正需要做的就是使用该类型签名简单地注释您已经拥有的函数.但是,没有(合理的/合理的)方式以某种方式引导Haskell从函数定义中推断出该类型,因为这需要以某种方式间接指示列表必须包含支持Integral...中的操作的类型的值.亚达.

最后要注意的是:你完全正确地实现了算法/算法,但是在类型签名和普遍性概念方面做得不够.

编辑:如果你真正需要的不是一个函数而是一个列表(你的问题在这方面有点模棱两可),你需要做的就是将下面的定义重命名myList为eg 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..].