[Haskell-beginners] Using my first map instance

[Harald Bögeholz]

Am 28.09.12 03:22, schrieb Darren Grant:
> Hi all,
> 
> I'm working on project euler problem 14, whose solution is the maximum
> Collatz chain length for all natural numbers less than 1-million.
[...]

> So I wrote the following instead:
[...]
>   collatz :: (Int, CollatzSubMap) -> ([Int], CollatzSubMap)
[...]

>   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.

Whenever you want to carry something along while walking through a list,
you can use a fold:

cmax :: ([Int], CollatzSubMap) -> Int -> ([Int], CollatzSubMap)
cmax (xs, m) y = (if length ys > length xs then ys else xs, m')
  where (ys, m') = collatz (y, m)

*Main> length $ fst $ foldl cmax ([], M.empty) [1..1000]
179

But I think I wouldn't do it this way. There is no need to keep all
those lists when you are only interested in their lengths. Also I have a
strong feeling a monad might be a good way to carry along the state
while focusing the code on the actual computation, but I still don't
fully understand those.


Harald