低于任何给定非负小数的最大整数

Question

我如何使用尾递归找到任何非负小数以下的最大中间体？

我已经largest :: Fractional f -> Int i定义了函数，但在这种情况下看不到如何使用尾递归。

Answer 1

任何Fractional都有一个类定义，例如：

class Num a => Fractional a where
    fromRational :: Rational -> a
    -- ...

跟：

type Rational = Ratio Integer

和：

(%) :: Integral a => a -> a -> Ratio a 

我还假设存在一个类型约束，以便我们可以比较(Fractional实例的两个f(。所以我们能做的是：

1. 从设置为0的累加器开始，
2. 构造一个值为累加器+1 的Rational，
3. 将该Rational转换为f类型，
4. 将构建的f与给定的f进行比较，
5. 如果该值大于给定的值，则我们返回累加器，
6. 否则，我们通过递增的累加器执行递归。

所以在代码中，这看起来像：

import Data.Ratio((%))
largest :: (Fractional a, Ord a) => a -> Integer
largest v = largest' 0
    where largest' x | fromRational (x1%1) >= v = x -- increment is less than or equal, return x
                     | otherwise = largest' x1 -- if smaller, recursion
              where x1 = x+1 -- increment accumulator

这给出了：

*Main Data.Ratio> largest (7%5)
1
*Main Data.Ratio> largest (21%5)
4
*Main Data.Ratio> largest (1%5)
0

如果你想在返回类型上有更多的自由度(任何Num，你可以在基写中添加fromIntegral(：

import Data.Ratio((%))
largest :: (Fractional a, Ord a, Num b) => a -> b
largest v = largest' 0
    where largest' x | fromRational (x1%1) >= v = fromIntegral x -- increment is less than or equal, return x
                     | otherwise = largest' x1 -- if smaller, recursion
              where x1 = x+1 -- increment accumulator