Haskell初学者: "No instance for...arising from..." error

Question

我的目标是编写一个函数来计算低于某个数字“n”的最大 Collat​​z 数。 (对于熟悉的人来说，这是一个欧拉计划问题。)

一些上下文:给定整数的 Collat​​z 数等于该整数的 Collat​​z 序列的长度。整数的 Collat​​z 序列计算如下:序列中的第一个数字(“n0”)是该整数本身；如果 n0 是偶数，则序列中的下一个数字(“n1”)等于 n/2；如果 n0 是奇数，则 n1 等于 3 * n0 + 1。我们继续递归扩展序列，直到到达 1，此时序列完成。例如，5 的 collat​​z 序列为:{5, 16, 8, 4, 2, 1}(因为 16 = 3 * 5 + 1, 8 = 16/2, 4 = 8/2,...)

我正在尝试编写一个函数(“maxCollat​​zUnder”)，当传递整数“m”时，它返回具有最长 Collat​​z 序列(即最大 Collat​​z 数)的整数(小于或等于 m) 。例如，maxCollat​​z 20(即低于(含)20 的哪个整数具有最长的拼贴序列？)应返回 19(数字 19 的 Collat​​z 序列长度为 21:[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) 为范围从 1 到 m 的每个整数 x 创建一个 2 元组 (x,y) 列表(其中 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 的父类(super class))，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类型。”

• “因此， n 中的 zip [1..n] (与 n 相同)必须是 RealFrac 类型，因此 [1..n] 是 RealFrac 的列表。”

• “因此， i 中的 (\acc (i,j) -> if j > acc then i else acc) 必定是 RealFrac 。”

• “由于上述 lambda 可以返回 i 或 acc，因此它们必须是同一类型。”

• “因为 j 正在与 acc 进行比较，所以 j 必须与 acc 具有相同的类型 - 因此与 i 和 RealFrac 具有相同的类型。”

• “但是等等 - j 是 collatzLength 的返回值，它是调用 length 的返回值，因此它必须是 Int ，但是Int 不在 RealFrac 中!”

• “错误!错误!”

我现在必须走了(编译器 cabal 不喜欢我泄露他们的 secret )，但最短的解决办法是不使用 truncate和/只需使用 div用于(取整)整数除法。