Collatz函数的实现

Question

给你一个哈斯克尔提到了Collatz序列：

我们取一个自然数。如果这个数字是偶数，我们除以2。如果它是奇数，我们把它乘以3，然后再加1。

当我试图实现它时，我遇到了一个问题。

collatz :: (Integral a) => a -> [a]
collatz x 
 | odd x    = f x : collatz (f x)
 | otherwise = g x : collatz (g x)
     where f y = y*3 + 1
           g y = y/2   

但是我得到了编译时错误：

CollatzSeq.hs:10:16:
Could not deduce (Fractional a) arising from a use of `g'
from the context (Integral a)
  bound by the type signature for collatz :: Integral a => a -> [a]
  at CollatzSeq.hs:7:12-35
Possible fix:
  add (Fractional a) to the context of
    the type signature for collatz :: Integral a => a -> [a]
In the first argument of `(:)', namely `g x'
In the expression: g x : collatz (g x)
In an equation for `collatz':
    collatz x
      | odd' x = f x : collatz (f x)
      | otherwise = g x : collatz (g x)
      where
          f y = y * 3 + 1
          g y = y / 2

据我所知，问题是调用collatz (g x)可以返回Fractional，因为y / 2返回Double

Prelude> let x = 4 / 2
Prelude> :t x
x :: Double

我试图通过在floor前面添加y/2来修复这个类型错误，但这是行不通的。

请告诉我如何纠正这个错误。

Answer 1

使用div而不是(/)。或者，如果您想要另一种舍入策略而不是floor，您可以使用fromIntegral，如

round (fromIntegral y / 2)

Answer 2

错误来自定义/的方式。GHCI显示了:t (/)的这个结果。

(/) :: Fractional a => a -> a -> a

另一种选择是使用div，它具有类型签名：

div :: Integral a => a -> a -> a

其次，您正在跳过当前实现中的输入项。情况不应如此。

最后，您需要添加输入= 1的大小写，否则函数将陷入无限循环。您可以将其更改为：

collatz :: (Integral a) => a -> [a]
collatz 1 = [1]
collatz x 
 | odd x    = x : collatz (f x)
 | otherwise = x : collatz (g x)
 where f y = y*3 + 1
       g y = y `div` 2