11

我一直在研究计算机程序的结构和解释，并在 Haskell 中完成练习。前两章很好（github 上的代码），但第 3 章让我更加努力地思考。

首先讨论管理状态，以银行账户为例。他们定义了一个make-withdraw函数

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

这样您就可以执行以下代码：

(define w1 (make-withdraw 100))
(define w2 (make-withdraw 100))

(w1 50)
50

(w2 70)
30

(w2 40)
"Insufficient funds"

(w1 40)
10

我不确定如何在 Haskell 中模拟这一点。我首先想到了一个使用 State monad 的简单函数：

import Control.Monad.State

type Cash    = Float
type Account = State Cash

withdraw :: Cash -> Account (Either String Cash)
withdraw amount = state makewithdrawal where
    makewithdrawal balance = if balance >= amount
        then (Right amount, balance - amount)
        else (Left "Insufficient funds", balance)

这允许我运行代码

ghci> runState (do { withdraw 50; withdraw 40 }) 100
(Left "Insufficient funds",30.0)

但这与方案代码有所不同。理想情况下，我可以运行类似的东西

do
  w1 <- makeWithdraw 100
  w2 <- makeWithdraw 100
  x1 <- w1 50
  y1 <- w2 70
  y2 <- w2 40
  x2 <- w1 40
  return [x1,y1,y2,x2]

[Right 50,Right 70,Left "Insufficient funds",Right 40]

但我不确定如何编写函数makeWithdraw。有什么建议吗？

4

2 回答 2

8

Scheme 代码偷偷使用了两个状态位：一个是变量和一个 ref-cell 之间的（隐式）w1关联w2；另一个是存储在参考单元中的（显式）状态。在 Haskell 中有几种不同的方法可以对此进行建模。例如，我们可以使用类似的 ref-cell 技巧ST：

makeWithdraw :: Float -> ST s (Float -> ST s (Either String Float))
makeWithdraw initialBalance = do
    refBalance <- newSTRef initialBalance
    return $ \amount -> do
        balance <- readSTRef refBalance
        let balance' = balance - amount
        if balance' < 0
            then return (Left "insufficient funds")
            else writeSTRef refBalance balance' >> return (Right balance')

这让我们可以这样做：

*Main> :{
*Main| runST $ do
*Main|   w1 <- makeWithdraw 100
*Main|   w2 <- makeWithdraw 100
*Main|   x1 <- w1 50
*Main|   y1 <- w2 70
*Main|   y2 <- w2 40
*Main|   x2 <- w1 40
*Main|   return [x1,y1,y2,x2]
*Main| :}
[Right 50.0,Right 30.0,Left "insufficient funds",Right 10.0]

另一种选择是使状态的两个部分都明确，例如通过将每个帐户与唯一的Intid 相关联。

type AccountNumber = Int
type Balance = Float
data BankState = BankState
    { nextAccountNumber :: AccountNumber
    , accountBalance :: Map AccountNumber Balance
    }

当然，我们基本上会重新实现 ref-cell 操作：

newAccount :: Balance -> State BankState AccountNumber
newAccount balance = do
    next <- gets nextAccountNumber
    modify $ \bs -> bs
        { nextAccountNumber = next + 1
        , accountBalance = insert next balance (accountBalance bs)
        }
    return next

withdraw :: Account -> Balance -> State BankState (Either String Balance)
withdraw account amount = do
    balance <- gets (fromMaybe 0 . lookup account . accountBalance)
    let balance' = balance - amount
    if balance' < 0
        then return (Left "insufficient funds")
        else modify (\bs -> bs { accountBalance = insert account balance' (accountBalance bs) }) >> return (Right balance')

然后让我们写makeWithdraw：

makeWithDraw :: Balance -> State BankState (Balance -> State BankState (Either String Balance))
makeWithdraw balance = withdraw <$> newAccount balance
于 2012-04-06T19:50:32.687 回答
4

好吧，这里有多个独立的、可变的状态：系统中的每个“帐户”都有一个。Statemonad 只允许你拥有一个状态。您可以在状态中存储类似的内容，每次(Int, Map Int Cash)递增以在地图中获取一个新键，并使用它来存储余额......但这太难看了，不是吗？Int

然而，值得庆幸的是，Haskell 有一个用于多个独立、可变状态的 monad ST：.

type Account = ST

makeWithdraw :: Cash -> Account s (Cash -> Account s (Either String Cash))
makeWithdraw amount = do
    cash <- newSTRef amount
    return withdraw
  where
    withdraw balance
        | balance >= amount = do
            modifySTRef cash (subtract amount)
            return $ Right amount
        | otherwise = return $ Left "Insufficient funds"

有了这个，您的代码示例应该可以正常工作；只是申请runST，你应该得到你想要的列表。STmonad 非常简单：你可以创建和修改s，它的STRef行为就像普通的可变变量一样；其实他们的界面和IORefs的界面基本一致。

唯一棘手的是额外的s类型参数，称为状态线程。这用于将每个STRef与ST它创建的上下文相关联。如果你可以STRef从一个ST动作中返回一个并将它带到另一个 ST上下文中，那将是非常糟糕的——关键ST是你可以在外面作为纯代码运行它的IO，但是如果STRefs 可以逃脱，那么您将在单子上下文之外拥有不纯的、可变的状态，只需将所有操作包装在runST! 因此，每个ST和STRef都携带相同的s类型参数，并且runST具有 type runST :: (forall s. ST s a) -> a。这会阻止您选择任何特定的值s：您的代码必须使用所有可能的值s。它从未分配任何特定类型；只是用作保持状态线程隔离的技巧。

于 2012-04-06T19:49:09.083 回答