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

31 Mar 2008

      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

chains n = List.foldl' (\m i -> Map.union m (chain m i))
(Map.singleton 1 1) [2..n]

maxCollatz c1@(_,l1) c2@(_,l2) | l1 < l2 = c2
                               | otherwise = c1

maxChain = List.foldl' maxCollatz (0,0) . Map.toList . chains

main =
    let n = 1000000
    in putStrLn $ show $ maxChain n

Best regards,

Bruno.

2008/3/31, Ketil Malde :
...
"Bruno Carnazzi"  writes:
...
The program ends for values up to 400000 :
Wild guess here - I know nothing about the problem, and haven't
 examined your program in detail - but could it be that you default to
 Int, and that it wraps silently at some power of two, thereby making
 your algorithm wrap around?  Try to stick some 'Integer' type
 annotations in there, and see if it helps.
-k
(cetera censeo...)
--
 If I haven't seen further, it is by standing in the footprints of giants