[Haskell-cafe] [Newbie] Problem with Data.Map (or something else ?)

[Luke Palmer]

On Mon, Mar 31, 2008 at 6:00 PM, Bruno Carnazzi <bcarnazzi at gmail.com> wrote:
> I've done this modification with no more success :
>
>  import qualified Data.List as List
>  import qualified Data.Map as Map
>
>  f :: Integer -> Integer
>
> f n | even n = n `div` 2
>     | otherwise = 3 * n + 1
>
>  chain m n =
>     let chain' cn cm | Map.member cn m = Map.map (+ (m Map.! cn)) cm
>                      | otherwise = chain' (f cn) $! Map.insert cn 1 (Map.map (+1) cm)
>     in chain' n Map.empty

This function raises a red flag for me.  The collatz sequence gets
_very_ big, with
very many distinct numbers.  You are saving the length of the
resulting chain for
each of those numbers, which is going to take a lot of memory.  But
Map is also lazy
in its values, so the values you are storing once chain finishes will look like:

   1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

Instead of 22, which is taking quite a lot of memory as well.

My impression is that the caching approach is just a bad idea.  It is
not necessary
to solve the problem efficiently; a brute force approach runs in under
1 minute in
constant memory for me.

Try to simplify your approach.  I'd suggest generating a list
representing the collatz
sequence starting at the number, then just taking its 'length'.  Do
that for each number
and find the maximum.  There should be no need for Data.Map.

Luke