查找一系列数字的排序规则序列

Question

我是Haskell的新手，我正在尝试解决Project Euler问题14。我还没有完成这个程序，但我所做的部分不起作用。这段代码应该打印出介于2和100之间的数字的Collatz序列的长度。

main = print $ collatzSeq [] [2..100]
collatzSeq xs (x:s) = collatzSeq (collatzLength x []):xs s
collatzLength x y
| x < 2 = length (x:y)
| even x = collatzLength (x / 2) (x / 2):y
| otherwise = collatzLength (3 * x + 1) (3 * x + 1):y

我尝试过以各种方式修改代码，我认为问题在于collatzLength函数。但从我目前对Haskell的了解来看，这个函数应该可以工作，但它不起作用，我也没有得到我所缺少的东西。我刚收到一个compiletime错误。

Answer 1

好吧，您的代码中有一些错误。这是哈斯克尔新手的常见错误。我列出如下：

1. 函数应用程序始终保持关联性，优先级高于所有运算符

因此，代码：

even x = collatzLength (x / 2) (x / 2):y

相当于

even x = (collatzLength (x / 2) (x / 2)):y

这显然是错误的，因为collatzLength的第二个自变量是[Int]，而不是Int

2. (/(函数或/运算符不能应用于Int类型或Num类

see(/(仅应用于作为Fractional实例的数据类型，而Int不是。在您的代码中，除法只适用于偶数，因此可以使用quot作为：

even x = collatzLength (x `quot` 2) ((x `quot` 2):y)

3. 缺少递归函数的基本情况

正如talex在评论中提到的，递归函数collatzSeq永远不会结束。因为它错过了指示函数应如何结束计算的基本情况。在您的情况下，通常会检查输入列表是否为空：

collatzSeq xs []    = xs
collatzSeq xs (x:s) = collatzSeq ((collatzLength x []):xs) s

最后，最好为函数提供类型签名，以使代码清晰可读。

把它们放在一起，修正看起来像：

collatzSeq::[Int]->[Int]->[Int]
collatzSeq xs []    = xs
collatzSeq xs (x:s) = collatzSeq ((collatzLength x []):xs) s
collatzLength::Int->[Int]->Int
collatzLength x y
| x < 2 = length (x:y)
| even x = collatzLength (x `quot` 2) ((x `quot` 2):y)
| otherwise = collatzLength (3 * x + 1) ((3 * x + 1):y)