[Haskell-beginners] Using my first map instance

Daniel Trstenjak daniel.trstenjak at gmail.com
Fri Sep 28 10:15:20 CEST 2012


Hi Darren,

On Thu, Sep 27, 2012 at 06:22:56PM -0700, Darren Grant wrote:
>   collatz 1 = [1]
>   collatz n = let next x | even x = x `div` 2 | otherwise = 3*x+1 in
> n:collatz (next n)

why creating a list if you're only interested in its length?
Something like a 'collatzLength' function could be suitable.

Instead of adding it to the list just increase an accumulator.

collatzLength n = go n 0
   where
      go n acc ...
      ...


or


collatzLength n lenCache = go n 0 lenCache
   where
      go n acc lenCache ...
      ...

>   import qualified Data.Map as M
> 
>   type CollatzSubMap = M.Map Int [Int]
> 
>   collatz :: (Int, CollatzSubMap) -> ([Int], CollatzSubMap)
>   collatz (1,m) = ([1], 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.

why creating a list if you only want its maximum value?

result = go 1 0 M.empty
   where
      go n maxLen lenCache ...
      ...


Greetings,
Daniel



More information about the Beginners mailing list