[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