2 similar Haskell functions using do notation return same result but one is called many more times

user_9464295 0
Viewed 66
nextState :: IO Int -> IO Int -- 0 1 0 2 0 1 0
nextState stateIO = do
  value <- stateIO
  putStrLn $ "Current state: " ++ show value
  fmap (+1) stateIO

nextState' :: IO Int -> IO Int -- 0 1 2
nextState' stateIO = do
  value <- stateIO
  putStrLn $ "Current state: " ++ show value
  return $ value + 1

main :: IO ()
main = do
  let startStateIO = return 0 :: IO Int
  let states = iterate nextState' startStateIO -- Use nextState or nextState'
  stateInt <- states !! 3
  print stateInt -- 3 in both cases

This Haskell code has 2 functions which both seemingly have identical behavior. However, printing calls shows that nextState is being called a lot more times than nextState'. I had a larger project where this was an issue and I couldn't figure out how to convert that function so that it was called the minimum number of times so I couldn't fix it.

Why does this happen and how can I prevent it in a less simple example?

Note that fmap (+1) in my actual project is just a function from IO a -> IO a, not fmap (a -> a) - the whole thing works in terms of IO, not modifying the values inside using (a->a)

recursion optimization haskell
1 Answers

It should be easier to understand this example, which is analogous:

twice :: IO () -> IO ()
twice act = do
   () <- act
   fmap id act -- like what you did in `nextState`

once :: IO () -> IO ()
once act = do
   () <- act
   return $ id ()  -- like what you did in `nextState'`

...or shorter

twice :: IO () -> IO ()
twice act = act >> act

once :: IO () -> IO ()
once act = act

For example,

> twice (putStrLn "hello")
hello
hello
> once (putStrLn "hello")
hello

Iterating once doesn't do anything, because it's just the identity.

> iterate once (putStrLn "hello") !! 4
hello

Iterating twice, however...

Prelude> iterate twice (putStrLn "hello") !! 4
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
user_7459030
Related