arrays - Haskell 可变数组未修改

Question

我正在解决Project Euler 的问题，我在14号。

我有一个可变IOArray的来存储我已经计算过的 Collat​​z 长度：

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)

其中第一个元素是正在计算的数字，第二个数字是其 Collat​​z 序列的长度。

问题是，在p14我做writeArray array i v，但它总是有一个零（0）数组。这是为什么？

Answer 1

我运行了您的确切代码，发现数组已更改。

因为末尾有很多零，您需要一直滚动到开头才能找到数字。

实际上，如果你替换

  frozen <- freeze array
  return $ elems frozen

和

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

你得到 525 这是正确的解决方案......更多关于最后的内容。

但是有几个问题：

1. 根据我的理解，在该行中forM_ col $ \(v,i) -> do，第一个值(v,i)是索引，第二个是值。(i,v)
2. 现在我们已经解决了这个问题，如果我们尝试使用forM_ [1..10]and运行代码newArray (1,10)，我们会得到*** Exception: Ix{Int}.index: Index (16) out of range ((1,10)). 一旦您1000000再次将值设置为 ，这也会发生，因为在某些情况下，为了计算数字的 collat​​z，您必须计算大于 的数字的 collat​​z 1000000。例如，collat​​z仅包含 4 步之后837798的计算。1885048尝试写入该索引会破坏事情。

对于第二种解决方案，您可以：

• 尝试制作一个绝对巨大的可变数组，希望您的 collat​​z 序列永远不会超出界限（我不建议这样做）
• 尝试制作一个不利用预计算值的幼稚版本（主要是让它工作，然后从那里正确优化）
• 拥有它，以便在每次写入之前执行绑定检查
• ...或者从头开始重新设计，看看你是否能想出一个更优雅的解决方案；）

起作用的原因length . takeWhile (/=0) $ sol是因为你使用(v,i)了而不是，所以你在索引 i(i,v)中写了一个 collat​​z 序列长度为 i 的最小数字，所以在索引 525 处你得到 837799，然后从那里开始它全为零，因为没有大于 525 的 collat​​z 序列。

Answer 2

万一这让你感到困惑，只是一个疯狂的预感：虽然p14修改了它使用的数组，但之后不会p14extra包含该数组。这是一个 IO 操作，每次运行时总是会创建一个新数组，其中填充零。

Answer 3

我不确定您所说的“不保持修改”是什么意思。

使用此代码（请注意，我已经更改了迭代和数组边界）：

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)

运行收益p14率ghci：

[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]