История изменений

import Data.Function
import Data.Vector.Unboxed.Mutable as V
import Text.Printf
import Control.Monad

main :: IO ()
main = do

{-
  let
    f 0 = 0
    f 1 = 1
    f n = let (d, m) = n `divMod` 2 in
      if m == 0 then f d + 1 else min (f d + 2) (f (d + 1) + 2)
-}

  mem :: IOVector Int <- V.replicate 2000000 0
  unsafeWrite mem 1 1

  let

    wrt arr ix val = unsafeWrite arr ix val >> return val

    f n = do
      e <- unsafeRead mem n
      if e > 0
      then return e
      else do
        let (d, m) = n `divMod` 2
        if m == 0
        then wrt mem n . (+1) =<< f d
        else wrt mem n =<< liftM2 (min `on` (+2)) (f d) (f (d + 1))
        --                 (min `on` (+2)) <$> f d <*> f (d + 1)
  forM_ [1 .. 1000000] $ \i -> printf "%i %i\n" i =<< f i

import Data.Function
import Data.Vector.Unboxed.Mutable as V
import Text.Printf
import Control.Monad

main :: IO ()
main = do

{-
  let
    f 0 = 0
    f 1 = 1
    f n = let (d, m) = n `divMod` 2 in
      if m == 0 then f d + 1 else min (f d + 2) (f (d + 1) + 2)
-}

  mem :: IOVector Int <- V.replicate 2000000 0
  unsafeWrite mem 1 1

  let

    wrt arr ix val = unsafeWrite arr ix val >> return val

    f n = do
      e <- unsafeRead mem n
      if e > 0
      then return e
      else do
        let (d, m) = n `divMod` 2
        if m == 0
        then wrt mem n . (+1) =<< f d
        else wrt mem n =<< liftM2 (min `on` (+2)) (f d) (f (d + 1))

  forM_ [1 .. 1000000] $ \i -> printf "%i %i\n" i =<< f i