CODEWITHSUNDEEP
haskell
teryret
teryret

Reputation: 240

project euler 14 using the state monad

I'm trying to teach myself Haskell (again) by working through Project Euler. Question 14 (https://projecteuler.net/problem=14) is begging for dynamic programming and historically I've been vehemently anti-monad (on account of repeatedly failing to learn to use them well enough to make life easier instead of harder) so I'm trying to bite the bullet and use the State monad to memoize my code... it's not going well. I want to be clear, I've already solved the problem the easy/slow way, at this point I'm trying to learn something (ie Project Euler No. 14 Haskell is not what I'm looking for).

My code so far is:

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)

which works for individual queries in cabal repl, but for the life of me I can't figure out how to chain up the state of repeated calls to collatzFast. I want something like

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

but I think this is inside out. Bind takes the result portion of the previous State computation and passes it to the next call, but I want it to take the state portion of the previous State computation and pass it to the next call.

Is there a right way to do this or have I painted myself into a corner? If I can't use >>=, what's the point of having a monad? ... or is there no point because this is a stupid approach? Help?

Upvotes: 2

Views: 161

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153162

You might like

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

In particular, mapM collatzFast :: [Int] -> State (Map Int Int) [Int].

Upvotes: 6

Related Questions