haskell - 使用状态 monad 的欧拉项目 14

Question

我正在尝试通过欧拉计划(Project Euler)自学 Haskell。问题 14 ( https://projecteuler.net/problem=14 ) 要求动态编程，而且从历史上看，我一直强烈反对 monad (因为我多次未能学会如何很好地使用它们来让生活变得更轻松而不是更困难)，所以我试图咬住子弹并使用 State monad 来内存我的代码......进展并不顺利。我想澄清一下，我已经以简单/缓慢的方式解决了问题，此时我正在尝试学习一些东西(即 Project Euler No. 14 Haskell 不是我正在寻找的)。

到目前为止我的代码是:

collatzMemoCheck :: Int -> State (Map Int Int) Int
collatzMemoCheck n = state $ \s -> maybe (let (a, s') = runState (collatzFast n) s
                                          in (a+1, Map.insert n (a+1) s'))
                                         (\len -> (len, s))
                                         (Map.lookup n s)

collatzFast :: Int -> State (Map Int Int) Int
collatzFast 1 = state $ \_ -> (1, Map.singleton 1 1)
collatzFast n
  | even n    = collatzMemoCheck (n `quot` 2)
  | otherwise = collatzMemoCheck (3 * n + 1)

它适用于 cabal repl 中的单个查询，但对于我来说，我无法弄清楚如何将重复调用的状态链接到 collat​​zFast。我想要类似的东西

-- DOES NOT WORK
allCollatzLengths = scanl (>>= collatzFast) (return Map.empty) [1..999999]

但我认为这是由内而外的。 Bind 获取上一个状态计算的结果部分并将其传递给下一个调用，但我希望它获取上一个状态计算的状态部分并将其传递给下一个调用。

是否有正确的方法来做到这一点，或者我把自己逼到了角落？如果我不能使用 >>=，那么拥有 monad 的意义何在？ ...或者因为这是一种愚蠢的方法而没有意义？帮忙？

Answer 1

你可能会喜欢

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

特别是，mapM collat​​zFast::[Int] -> State (Map Int Int) [Int]。