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

Question

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

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

Answer 1

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

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

有：

type Rational = Ratio Integer

和：

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

我还假设存在类型约束，这样我们就可以比较两个f（属于Fractional 实例）。那么我们能做的是：

从设置为 0、
构造一个 Rational 其值为 accumulator+1,
将 Rational 转换为 f 类型，
将构造的f与给定的f、
如果值大于给定值，那么我们return累加器，
否则，我们通过递增的累加器执行递归。

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

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

如果你想要更多关于 return 类型的自由（任何 Num，你可以在 basecase 中添加 fromIntegral）：

import Data.Ratio((%))

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

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

Largest integer below any given non-negative fractional number

haskell

recursion

functional-programming

tail-recursion