使用命令式编程的阶乘

Question

我有以下代码：

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 ()

我需要使用命令式编程来实现阶乘函数。我要做的是使用 newIORef 创建和初始化变量，使用带有 readIORef 和 writeIORef 的 while 循环修改它们的值，然后让 IO 动作 return 由输入 n 和最终结果

组成的一对

这是我到目前为止所做的：

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

这是我写阶乘函数的尝试。这显然是行不通的。任何帮助将不胜感激。

Answer 1

我想也许是时候给你一些工作版本了：

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)

如你所见，我使用了一个 loop 参考 i 和一个 accumulator 参考 acc 一直在阅读, 写入变化的值。

为了（希望）使位更具可读性，我将while的test和body提取到lessOrEqualN 和 step.

当然有更简单的方法来做到这一点 (modifyIORef) 但我想你必须使用那些。

PS：你稍微玩一下 - 也许你想以不同的方式处理负值或其他什么

这可能更简洁（将两个 mutables 放入同一个 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)

Answer 2

我认为 Carsten 的回答可以像这样更简洁一些：

{-# 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

我在这里做的是：

使用 modifyIORef 减少配对 readIORef/writeIORef 调用的数量。
使用fmap减少对辅助函数测试IORef内容的需要。
编写一个通用的、可重复使用的 postIncrement 函数并使用它进一步缩短 fact。

但坦率地说，我认为您的讲师坚持要您使用此 while 功能有点愚蠢。它不利于干净的代码。如果有人告诉我用 IORef 写命令式阶乘，我会先写这个，只使用库中的 forM_ 循环：

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

那是因为我太笨了，无法立即记住 replicateM_ :: Monad m => Int -> m a -> m ()...

使用命令式编程的阶乘

Factorial using imperative-style programming

haskell

imperative-programming