Haskell 中的 Tribonacci 序列 [Monads？]

Question

trib :: Int -> Int  
trib 1 = 1  
trib 2 = 1  
trib 3 = 2   
trib n | n > 3 = trib (n-3) + trib (n-2) + trib (n-1)    

此代码生成 Tribonacci 序列，但这非常慢

如何使用 State Monad 做类似的事情并且花费更少的时间？

使用教科书上的斐波那契代码后，我得到了一个基本框架，但不确定 stateTrib 操作

stateTrib :: Integer -> State (Integer,Integer,Integer) ()
 stateTrib = ??? 
 runStateTrib :: Integer -> Integer
 runStateTrib n = let ((),(a,b,c)) = (runState (stateTrib n) (1,0,0)) in a

Answer 1

你不需要

State

来有效地解决它，只需使用简单的递归来更新累加器：

trib (a, _, _) 1 = a
trib (_, b, _) 2 = b
trib (_, _, c) 3 = c
trib (a, b, c) n = trib (b, c, a + b + c) (n - 1)

但是如果你真的想参与

State

，那么变化主要在于累加器的访问方式：

stateTrib 1 = gets $ \(a, _, _) -> a
stateTrib 2 = gets $ \(_, b, _) -> b
stateTrib 3 = gets $ \(_, _, c) -> c
stateTrib n = do
  (a, b, c) <- get
  put (b, c, a + b + c)
  stateTrib (n - 1)

请注意，

State

版本可能比普通递归慢（不确定优化器将如何处理它）。