Haskell初学者:"没有......来自...的错误."错误

Question

我的目标是编写一个函数来计算低于某个数字'n'的最大Collat​​z数.(对于那些熟悉的人来说,这是一个项目欧拉问题.)

某些上下文:给定整数的Collat​​z数等于该整数的Collat​​z序列的长度.整数的Collat​​z序列计算如下:序列中的第一个数字("n0")是整数本身; 如果n0是偶数,则序列中的下一个数字("n1")等于n/2; 如果n0是奇数,那么n1等于3*n0 + 1.我们继续递归地扩展序列,直到我们到达1,此时序列结束.例如,5的折叠序列是:{5,16,8,4,2,1}(因为16 = 3*5 + 1,8 = 16/2,4 = 8/2,...)

我正在尝试编写一个函数("maxCollat​​zUnder"),当传递一个整数"m"时,它返回一个整数(小于或等于m),它具有最长的Collat​​z序列(即最大的Collat​​z数).例如,maxCollat​​z 20(即,低于(包括)20的整数具有最长的拼贴序列？)应该返回19(数字19具有长度为21的Collat​​z序列:[19,58,29,88,44,22, 11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]).

在下面的代码中,"collat​​z"和"collat​​zHelper"函数可以正确编译和运行.我在使用"maxCollat​​zUnder"功能时遇到了麻烦.该函数旨在(I)为每个整数x创建一个2元组(x,y)的列表,范围从1到m(其中m是函数参数),其中y表示整数x的Collat​​z数,然后( II)查看列表中最高的Collat​​z数(即y)并返回其相关的整数(即x)

maxCollatzUnder n = foldl(\acc (i,j) -> if j > acc then i else acc) 0 
    (zip [1..n] ( map collatzLength [1..n]))
    where collatzLength n = length . collatz $ n

collatz n = map truncate $ collatzHelper n

collatzHelper 0 = [0]
collatzHelper 1 = [1]
collatzHelper n
    | (truncate n) `mod` 2 == 0 = [n] ++ collatzHelper (n/2)
    | otherwise = [n] ++ collatzHelper (3*n+1)

我(尝试)编译时出现以下错误.

*Main> :l PE14Collatz.hs
[1 of 1] Compiling Main             ( PE14Collatz.hs, interpreted )

PE14Collatz.hs:7:89:
    No instance for (RealFrac Int)
      arising from a use of `collatzLength'
    In the first argument of `map', namely `collatzLength'
    In the second argument of `zip', namely
      `(map collatzLength [1 .. n])'
    In the third argument of `foldl', namely
      `(zip [1 .. n] (map collatzLength [1 .. n]))'
Failed, modules loaded: none.

令人好奇的是,如果我将"maxCollat​​zUnder"更改为以下代码(见下文),代码将编译并正确运行.唯一的变化是,在下面的版本中,fold函数返回"j"(即最大的Collat​​z数)而不是"i"(即生成最大Collat​​z数的整数).

maxCollatzUnder n = foldl(\acc (i,j) -> if j > acc then j else acc) 0 
    (zip [1..n] ( map collatzLength [1..n]))
    where collatzLength n = length . collatz $ n

尽管我仍然有兴趣了解这个错误的原因,但欢迎提出更有效/更优雅的方法.

Answer 1

由于您使用了truncate(一种方法RealFrac)和/(一种方法Fractional,一种超类RealFrac),Haskell为您的最后两个函数推断出以下两种类型的签名:

collatz :: (RealFrac a, Integral b) => a -> [b]
collatzHelper :: RealFrac a => a -> [a]

然后Haskell试图推断出它的类型maxCollatzUnder,它的思维过程如下:

• "在collatzLength n = length . collatz $ n,我们传递n给collatz,所以参数collatzLength必须是一个RealFrac."

• "因此,在map collatzLength [1..n],[1..n]必须是一个列表RealFrac值."

• "因此,n在map collatzLength [1..n]必须是RealFrac类型".

• "因此,nin zip [1..n](它是相同的n)必须是一个RealFrac类型,因此[1..n]是一个RealFracs 的列表."

• "因此,i在(\acc (i,j) -> if j > acc then i else acc)必须是一个RealFrac."

• "因为前面提到的lambda可以返回,i或者acc它们必须是同一类型."

• "因为j正在进行比较acc,j必须与之相同acc- 因此i与a和a 相同RealFrac."

• "但是等待 - j是来自的返回值collatzLength,这是一个调用的返回值length,所以它必须是一个Int,但Int不是RealFrac! "

• "错误!错误!"

我现在得走了(编译惊天动地不喜欢我放弃自己的秘密),但最短的解决方法是不使用truncate和/,只是使用div的(地板),整数除法.