Haskell [Monads？]中的Tribonacci序列

irtuqstp 于 2022-12-13 发布在其他

关注(0)|答案(1)|浏览(115)

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序列，但是速度非常慢
如何使用状态单子来做类似的事情，并且花费更少的时间？
在使用教科书中的斐波那契代码后，我能够得到一个基本的 backbone ，但不确定statTrib操作

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

haskell

来源：https://stackoverflow.com/questions/74702589/tribonacci-sequence-in-haskell-monads

1条答案

按热度按时间

j5fpnvbx1#

你不需要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版本更可能比普通递归慢（不确定优化器如何处理它）。

赞(0）回复(0）举报 2022-12-13

我来回答

Haskell [Monads？]中的Tribonacci序列

1条答案

相关问题

热门标签

最新问答