Haskell Mutable Array not modified

Question

I'm doing the Project Euler's problems and I'm on the 14th.

I have a mutable IOArray to store the Collatz lengths that I have already calculated:

import Data.Array.IO
import Control.Monad
import Data.Array

p14 :: IO [Int]
p14 = do
  array <- p14extra
  forM_ [1..1000000] $ \i -> do
    e <- readArray array i
    if e == 0
      then do
        let col  = collatz i
        forM_ col $ \(v,i) -> do
          writeArray array i v
      else return ()
  frozen <- freeze array
  return $ elems frozen

-- an `IOArray` from `1` to `1000000` full of `0`
p14extra :: IO (IOArray Int Int)
p14extra = newArray (1,1000000) 0

collatz :: Int -> [(Int, Int)]
collatz n
  | n == 1    = [(1,1)]
  | otherwise = (n, (snd $ head hack) + 1) : hack
  where
    hack = collatz $ if even n then (n `div` 2) else (3 * n + 1)

where the first element is the number being calculated and the second number is the length of its Collatz sequence.

The thing is that in p14 I do writeArray array i v but it always has an array of zeros (0s) in it. Why is that?

please include your import statements and type signatures for functions — ErikR
– ErikR, Commented Nov 4, 2013 at 7:29
What makes you think that the array is not staying modified? Have you tried printing the contents of the modified cells before and after writeArray? — Mikhail Glushenkov
– Mikhail Glushenkov, Commented Nov 4, 2013 at 7:29
what's up with the downvotes? Clearly asked, code included, few English mistakes is all. ... Well, imports are missing... — Will Ness
– Will Ness, Commented Nov 4, 2013 at 14:01

Alex Appetiti · Accepted Answer · 2013-11-04 09:37:40Z

I ran your exact code, and found that the array was changed.

Because there are a lot of zeros at the end, you need to scroll all the way up to the beginning to find the numbers.

Actually, if you substitute

  frozen <- freeze array
  return $ elems frozen

with

  sol <- getElems array
  return (length . takeWhile (/=0) $ sol)

You get 525 which is the correct solution... more about that towards the end.

There are a couple of problems though:

In the line forM_ col $ \(v,i) -> do, (v,i) should be (i,v) seeing as in collatz from what I understand the first value is the index, and the second is the value.
Now that we've sorted that out, if we try running the code with forM_ [1..10] and newArray (1,10), we get *** Exception: Ix{Int}.index: Index (16) out of range ((1,10)). This will also happen once you set the values to 1000000 again as there will be occasions in which in order to compute the collatz of a number, you must compute the collatz of a number greater than 1000000. For example, the collatz of 837798 includes the calculation of 1885048 after only 4 steps. Trying to write to that index will break things.

For the second solution, you could:

Try and make an absolutely gigantic mutable array in the hopes that your collatz sequences never go over the bounds (I don't suggest it)
Try and make a naive version that doesn't take advantage of precomputed values (mainly to get it working, then from there optimise properly)
Have it so that before each write, a bound check is performed
...Or redesign things from scratch and see if you can come up with a more elegant solution ;)

The reason why length . takeWhile (/=0) $ sol works is that because you used (v,i) instead of (i,v), you were writing the lowest number with a collatz sequence length i, in index i, so at index 525 you got 837799, then from there onwards it was all zeros, as there is no collatz sequence which is larger than 525.

ErikR · Accepted Answer · 2013-11-04 07:37:17Z

I'm not sure what you mean by "is not staying modified".

Using this code (note that I've changed the iteration and array bounds):

import Control.Monad (forM_)
import Data.Array.IO
import Data.Array

p14 :: IO [Int]
p14 = do
  array <- p14extra
  forM_ [1..10] $ \i -> do
    e <- readArray array i
    if e == 0
      then do
        let col  = collatz i
        forM_ col $ \(v,i) -> do
          writeArray array i v
      else return ()
  frozen <- freeze array
  return $ elems frozen

p14extra :: IO (IOArray Int Int)
p14extra = newArray (1,100) 0

collatz :: Int -> [(Int, Int)]
collatz n
  | n == 1    = [(1,1)]
  | otherwise = (n, (snd $ head hack) + 1) : hack
  where
    hack = collatz $ if even n then (n `div` 2) else (3 * n + 1)

running p14 in ghci yields:

[1,2,4,8,16,5,10,20,40,13,26,52,17,34,11,22,7,14,28,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Ørjan Johansen · Accepted Answer · 2013-11-05 02:32:32Z

1

Just a wild hunch in case this is what is confusing you: Although p14 modifies the array it uses, p14extra will not contain that array afterwards. It is an IO action which will always create a new array filled with zeros each time it is run.

answered Nov 5, 2013 at 2:32

Ørjan Johansen

18.2k3 gold badges45 silver badges53 bronze badges

Collectives™ on Stack Overflow

Haskell Mutable Array not modified

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related