[Haskell-beginners] Using my first map instance
therealkludgy at gmail.com
Fri Sep 28 03:22:56 CEST 2012
I'm working on project euler problem 14, whose solution is the maximum
Collatz chain length for all natural numbers less than 1-million.
The naive approach takes too long to execute:
collatz 1 = 
collatz n = let next x | even x = x `div` 2 | otherwise = 3*x+1 in
n:collatz (next n)
result = maximum [length (collatz x) | x <- [1..999999]]
I know there are a handful of approaches to take to reduce computation
time, but in this case I am focusing on exploiting fast recollection
of previously computed sub-chain lengths in a map.
So I wrote the following instead:
import qualified Data.Map as M
type CollatzSubMap = M.Map Int [Int]
collatz :: (Int, CollatzSubMap) -> ([Int], CollatzSubMap)
collatz (1,m) = (, m)
collatz (n,m) = let next x | even x = x `div` 2 | otherwise = 3*x+1 in
case M.lookup n m of
Nothing -> let (ns,m') = collatz (next n, m) in (n:ns, M.insert n (n:ns) m')
Just ns -> (ns,m)
result = maximum [length $ fst $ collatz (x, M.empty) | x <-
[1..999999] :: [Int]]
Where I'm currently stumped is in feeding the resulting map from one
call to collatz into the next iteration in the list comprehension;
that M.empty should carry the end result of previous iterations.
Can anyone point me in the right direction? Other criticisms of the
code are also welcome.
More information about the Beginners