[Haskell-beginners] Using my first map instance
Darren Grant
therealkludgy at gmail.com
Sat Sep 29 00:15:24 CEST 2012
On Fri, Sep 28, 2012 at 1:15 AM, Daniel Trstenjak
<daniel.trstenjak at gmail.com> wrote:
>
> 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
Thanks for the advice.
I've been looking into memoization techniques for Haskell and am
currently trying different approaches. The version below is my current
attempt, a no-go right off the bat because of the dense fromList
domain. However, the simplicity of the expressions is nice. Is there
an elegant mechanism that can replace the fromList comprehension that
will only process exactly the values requested? It seems a bit much
to ask, and I'm beginning to suspect that imperative approaches are
better for solving this particular memo problem.
collatzSucc x | even x = x `div` 2 | otherwise = 3*x+1
collatzLenCache = M.fromList [(x, collatzLen x) | x <- [1..]]
collatzLen :: Integer -> Int
collatzLen 1 = 1
collatzLen x = (collatzLenCache M.! (collatzSucc x)) + 1
result = maximum [collatzLen x | x <- [1..999999]]
Cheers,
Darren
More information about the Beginners
mailing list