2

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

一些上下文：给定整数的 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 具有长度为 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) 为从 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”更改为以下代码（见下文），代码可以正确编译并运行。唯一的变化是，在下面的版本中，折叠函数返回“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

欢迎提出更有效/更优雅的方法的建议，尽管我仍然有兴趣了解此错误的原因。

4

1 回答 1

6

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

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

Haskell 然后尝试推断 的类型maxCollatzUnder，其思考过程如下：

  • “在collatzLength n = length . collatz $ n中，我们传递n给collatz，所以参数 tocollatzLength必须是RealFrac。”

  • “因此， in map collatzLength [1..n]，[1..n]必须是RealFrac值列表。”

  • “因此，ninmap collatzLength [1..n]必须是一个RealFrac类型。”

  • “因此，nin zip [1..n]（相同的n）必须是一种RealFrac类型， s[1..n]的列表也是如此RealFrac。”

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

  • “因为前面提到的 lambda 可以返回ior acc，所以它们必须是相同的类型。”

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

  • “但是等等——j是来自 的返回值collatzLength，它是对 的调用的返回值length，所以它必须是一个Int，但Int不在RealFrac！ ”

  • “错误！错误！”

我现在得走了（编译器阴谋集团不喜欢我泄露他们的秘密），但最短的解决办法是不使用truncate并且/只div用于（下限）整数除法。

于 2014-10-02T02:29:14.380 回答