Mutable IORef-based factorial example in Haskell

Question

Here is my attempt to write the infamous factorial using Data.IORef.

import Data.IORef

xgo accRef nRef = go where
  go = do
    acc <- readIORef accRef
    n <- readIORef nRef
    writeIORef accRef (acc * n)
    writeIORef nRef (n - 1)
    if (n > 2) then go else readIORef accRef
       
facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  xgo accRef nRef

This code is supposed to be an example for dummies on how to use IORefs, so certainly I want to keep it simple -- e.g. no tuples and no lens. But the whole xgo thing seem artificial. Can we have xgo defined within facM? What is the most idiomatic way to write IORef code like this (of course I don't mean avoiding IORef, we all know the fac n = prod [1..n] solution here).

Upd: I got it to:

facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  let xgo = go where {
    go = do
      acc <- readIORef accRef
      n <- readIORef nRef
      writeIORef accRef (acc * n)
      writeIORef nRef (n - 1)
      if (n > 2) then go else readIORef accRef
  }
  xgo

So there are no second accRef/nRef anymore, but there is still this xgo/go separation. Somehow I can't get xgo = do { ... } working without an intermediate go

Sara J · Accepted Answer · 2023-02-21 19:10:44Z

First off, there a bug, if not a very significant one - 0! is meant to be 1, but the current code returns 0. Checking if n > 1 before you do any multiplication would get around this.

Second, since acc is only ever used for updating accRef, I feel it might be cleaner to use modifyIORef instead of a readIORef followed by a writeIORef. This wouldn't apply to nRef, though, since n is actually used in multiple places

Also, I'd like to see explicit type signatures added to any top-level functions (facM and, in the original code, xgo). I find that knowing the exact type of a value often makes it much easier to understand what it is and why.

Finally, you mention being able to merge the separate xgo function into facM, but ended up having to also have an effectively identical go function to make it work. I think that might've been you running into haskell's notoriously confusing indentation rules. For instance, the following won't work:

import Data.IORef

facM :: (Num a, Ord a) => a -> IO a
facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  let go = do
    n <- readIORef nRef
    if n > 1 then do
      modifyIORef accRef (* n)
      writeIORef nRef (n - 1)
      go
    else readIORef accRef
  go

because the content of that do block is to the left of the name it is bound to (go). However, either of the following will work, because the block is indented further than the name it is bound to:

import Data.IORef

facM :: (Num a, Ord a) => a -> IO a
facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  let
    go = do
      n <- readIORef nRef
      if n > 1 then do
        modifyIORef accRef (* n)
        writeIORef nRef (n - 1)
        go
      else readIORef accRef
  go

import Data.IORef

facM :: (Num a, Ord a) => a -> IO a
facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  let go = do
        n <- readIORef nRef
        if n > 1 then do
          modifyIORef accRef (* n)
          writeIORef nRef (n - 1)
          go
        else readIORef accRef
  go

max taldykin · Accepted Answer · 2023-02-22 12:29:18Z

Not sure what you are trying to accomplish but you can replace explicit loop with mfix from Control.Monad.Fix.

import Data.IORef
import Control.Monad.Fix (mfix)

facM :: Int -> IO Int
facM n = do
  accRef <- newIORef 1
  nRef <- newIORef n
  mfix
    (\loop _ -> do
      m <- readIORef nRef
      acc <- readIORef accRef
      modifyIORef accRef (* m)
      modifyIORef nRef (subtract 1)
      if m > 2 then loop else readIORef accRef
    )
    undefined

This has scary undefined (which can be replaced by ()) so definitely not a good example for dummies.

Or like this if you want to confuse them even more:

facM :: Int -> IO Int
facM n
  = newIORef (n, 1)
  >>= mfix (\loop ref -> do
    (m, acc) <- readIORef ref
    writeIORef ref (m - 1, acc * m)
    if (m > 2) then loop else pure (acc * m)
  )

nponeccop · Accepted Answer · 2023-02-25 12:08:59Z

Thanks to essential hints by @sara-j, I ended up with the following:

import Data.IORef
import Control.Monad
       
facM nn = do
  accRef <- newIORef 1
  nRef <- newIORef nn
  let
    go = do
      n <- readIORef nRef
      when (n > 1) $ do
        modifyIORef accRef (\x -> x * n)
        modifyIORef nRef (\x -> x - 1)
        go
  go
  readIORef accRef

The code works well as an example for dummies because it corresponds to the following imperative code:

function facM(nn) {
  let acc = 1
  let n = nn
  while (n > 1) {
     acc *= n
     n -= 1
  }
  return acc
}

And moreover, we can then learn to abstract the loop away:

whileM cond block = go where
  go = do
    x <- cond
    when x $ do
      block
      go

(and this is what whileM from monad-loop already does)

Stack Exchange Network

Mutable IORef-based factorial example in Haskell

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Mutable IORef-based factorial example in Haskell

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions