On Fri, Sep 28, 2012 at 1:15 AM, Daniel Trstenjak 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

On Fri, Sep 28, 2012 at 4:57 PM, Sean Perry wrote:

On Sep 28, 2012, at 3:15 PM, Darren Grant wrote:

...

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.

Have you looked at http://www.haskell.org/haskellwiki/Euler_problems/11_to_20#Problem_14?

The page is full of interesting and fast solutions once you have worked out your own versions.

Hah I didn't know the Haskell Wiki had a Project Euler page. I'll definitely be reviewing with that resource. I notice the use of Array instead of Map, and the careful use of unboxed types. :) Cheers, Darren

On Sat, Sep 29, 2012 at 2:36 AM, Chaddaï Fouché wrote:

On Sat, Sep 29, 2012 at 2:44 AM, Darren Grant wrote:

...

On Fri, Sep 28, 2012 at 4:57 PM, Sean Perry wrote:

...

Have you looked at http://www.haskell.org/haskellwiki/Euler_problems/11_to_20#Problem_14?

The page is full of interesting and fast solutions once you have worked out your own versions.

Hah I didn't know the Haskell Wiki had a Project Euler page. I'll definitely be reviewing with that resource.

I notice the use of Array instead of Map, and the careful use of unboxed types. :)

This comment is misleading, there are no unboxed type in this solution (maybe the author meant that this compiled down to unboxed types with optimisations but the Haskell code definitely use boxed types : Int and Word32) though there's a little bit of parallelism involved (could be improved).

You are correct. Thanks for pointing out the distinction between compiler optimizing down to unboxed types and actually declaring these types in code.

The use of a functional (immutable) Array here makes perfect sense since the keys are effectively an interval of Int... Note that my old Array version rely on the laziness of the Array to make it work, this is basically dynamic programming where the order of computation appears natural but only because laziness means it will be determined by the computation itself. This is perfectly functional, no need to resort to any imperative style here (or most everywhere in project Euler).

-- Jedaï

This is exactly the kind of recursive function I was trying to set up with map, but didn't get the algorithm right. I expect the immutable Array must be much lighter weight than the immutable Map. Cheers, Darren