项目欧拉14使用州monad

Question

我试图通过Project Euler来自学Haskell(再次).问题14(https://projecteuler.net/problem=14)正在乞求动态编程,而且从历史上来说,我一直强烈反对monad(因为我一再学会如何使用它们以使生活更轻松而不是更难所以我试图咬紧牙关并使用状态monad来记忆我的代码...它进展不顺利.我想清楚,我已经解决了这个问题的简单/缓慢的方式,此时我正在尝试学习一些东西(即项目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]

但我认为这是内在的.绑定发生之前的状态计算的结果部分,并将其传递到下一个电话,但我想它拿以前的状态计算的静态部分,并通过它的下一个电话.

有没有正确的方法来做到这一点,还是我把自己画成一个角落？如果我不能使用>> =,有一个monad是什么意思？......或者没有意义,因为这是一种愚蠢的做法？救命？

Answer 1

你可能会喜欢

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

特别是mapM collatzFast :: [Int] -> State (Map Int Int) [Int].