实现Collatz函数

Question

Learn You a Haskell提到Collatz Sequences:

我们取一个自然数。如果这个数字是偶数，我们就把它除以二。如果它是奇数，我们将它乘以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

我试图通过在y/2前面添加floor来修复这种类型的错误，但没有成功。

请告诉我如何修复这个错误。

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

其次，您正在跳过当前实现中的输入项。事实并非如此。

最后，您需要添加input=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