CODEWITHSUNDEEP
haskellimperative-programming
user3055141
user3055141

Reputation: 109

Factorial using imperative-style programming

I have the following code:

while :: IO Bool -> IO () -> IO ()
while test body =
  do b <- test
     if b
       then do {body ; while test body}  -- same-line syntax for do
       else return ()

I need to implement the factorial function using imperative-style programming. what I have to do is to create and initialize variables using newIORef, modify their values using a while loop with readIORef and writeIORef, then have the IO action return a pair consisting of the input n and the final result.

This is what I have done so far:

fact :: Integer -> IO (Integer, Integer)
fact n = do r <- newIORef n --initialize variable
            while
              (do {v <- readIORef n; n})
              (do {v <- readIORef r; writeIORef (...)) --modify the value (?)
            readIORef r

This is my attempt to write the factorial function. This is obviously does not work. Any help would be appreciated.

Upvotes: 3

Views: 454

Answers (2)

Luis Casillas
Luis Casillas

Reputation: 30227

I think Carsten's answer can be made a bit cleaner like this:

{-# LANGUAGE TupleSections #-}

import Control.Monad
import Data.IORef

fact :: Integer -> IO (Integer, Integer)
fact n = do
  counter <- newIORef 1
  result <- newIORef 1
  while (fmap (<=n) (readIORef counter)) $ do
    i <- postIncrement counter
    modifyIORef result (*i)
  fmap (n,) (readIORef result)

while :: IO Bool -> IO () -> IO ()
while test body =
  do b <- test
     if b
       then do {body ; while test body}  -- same-line syntax for do
       else return ()

postIncrement :: Enum a => IORef a -> IO a
postIncrement ref = do
  result <- readIORef ref
  modifyIORef ref succ
  return result

What I'm doing here is:

  1. Using modifyIORef to cut down on the number of paired readIORef/writeIORef calls.
  2. Using fmap to reduce the need for auxiliary functions to test the contents of an IORef.
  3. Write a generic, reusable postIncrement function and use that to shorten fact further.

But frankly, I think your instructor's insistence that you use this while function is a bit silly. It doesn't make for clean code. If I was told to write an imperative factorial with IORef I'd first write this, just using the forM_ loop from the library:

factorial :: Integer -> IO (Integer, Integer)
factorial n = do
  result <- newIORef 1
  forM_ [2..n] $ \i -> do
    modifyIORef result (*i)
  fmap (n,) (readIORef result)

And that's because I was too dumb to remember replicateM_ :: Monad m => Int -> m a -> m () right away...

Upvotes: 1

Random Dev
Random Dev

Reputation: 52270

I think maybe it's time to give you some working version:

fact :: Integer -> IO (Integer, Integer)
fact n = do
  i <- newIORef 1
  acc <- newIORef 1
  while (lessOrEqualN i) (step i acc)
  acc' <- readIORef acc
  return $ (n, acc')
  where
     lessOrEqualN iRef = do
       i' <- readIORef iRef
       return $ i' <= n
     step iRef accRef = do
       i' <- readIORef iRef
       acc' <- readIORef accRef
       writeIORef accRef (acc' * i')
       writeIORef iRef (i'+1)

as you can see I used an loop reference i and an accumulator reference acc always reading, writing the changing values.

To make this (hopefully) a bit more readable I extracted the test and the body of the while into lessOrEqualN and step.

Of course there are easier ways to do this (modifyIORef) but I guess you have to use those.

PS: you play with it a bit - maybe you want to handle negative values differently or whatever

this might be a bit cleaner (putting both mutables into the same ref):

fact :: Integer -> IO (Integer, Integer)
fact n = do
  ref <- newIORef (1,1)
  while (lessOrEqualN ref) (step ref)
  (_,acc) <- readIORef ref
  return $ (n, acc)
  where
     lessOrEqualN ref = do
       (i,_) <- readIORef ref
       return $ i <= n
     step ref = do
       (i,acc) <- readIORef ref
       writeIORef ref (i+1, acc * i)

Upvotes: 3

Related Questions