Haskell中使用State Monad优化低效Tribonacci序列实现

原递归实现之所以慢，是因为它会重复计算大量子问题——比如计算trib(n)时，会递归调用trib(n-1)、trib(n-2)、trib(n-3)，而这些子调用又会重复计算更低阶的项，时间复杂度是指数级的。用State Monad可以通过迭代式的状态保存，避免重复计算，把时间复杂度降到O(n)。

完整实现代码 #

首先导入State Monad的依赖模块：

import Control.Monad.State

然后实现核心的状态转换和迭代逻辑：

-- 单次状态转换：将当前三元组状态更新为下一组关联的Tribonacci值
nextTrib :: State (Integer, Integer, Integer) ()
nextTrib = do
    (x, y, z) <- get  -- 获取当前保存的状态三元组
    put (x + y + z, x, y)  -- 更新状态：新的第一项是前三项之和，后两项依次前移

-- 根据n的值，重复执行对应次数的状态转换
stateTrib :: Integer -> State (Integer, Integer, Integer) ()
stateTrib 1 = return ()  -- n=1时无需转换，初始状态的第一项就是结果
stateTrib n = do
    nextTrib
    stateTrib (n - 1)

-- 对外的调用入口，初始状态对应trib(1)=1、辅助边界值trib(0)=0、trib(-1)=0
runStateTrib :: Integer -> Integer
runStateTrib n = let ((), (a, _, _)) = runState (stateTrib n) (1, 0, 0) in a

逻辑说明 #

1. 状态定义：用三元组(x,y,z)保存三个连续的关联值，其中x是当前目标项，y、z分别是前一项和前两项。初始状态(1,0,0)是为了适配迭代规则定义的边界值。
2. 转换规则：每次执行nextTrib，会根据Tribonacci的递推公式trib(k) = trib(k-1)+trib(k-2)+trib(k-3)，生成下一组三元组，确保每一步都只基于已计算的结果推进。
3. 迭代次数：n=1直接返回初始状态的x；n>1时执行n-1次转换，逐步推导到目标项。

测试验证 #

main = do
    print $ runStateTrib 1  -- 输出1，对应原trib(1)
    print $ runStateTrib 2  -- 输出1，对应原trib(2)
    print $ runStateTrib 3  -- 输出2，对应原trib(3)
    print $ runStateTrib 4  -- 输出4，对应原trib(4)
    print $ runStateTrib 5  -- 输出7，对应原trib(5)

内容的提问来源于stack exchange，提问作者Aavesh