问题 管理国家 - SICP第3章
我一直在努力 计算机程序的结构与解释 并完成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。任何建议？
11559
2018-04-06 19:21
起源
答案:
Scheme代码偷偷地使用两位状态：一个是变量之间的（隐式）关联 w1 和 w2 和ref-cell;另一个是存储在ref-cell中的（显式）状态。在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]
另一种选择是使状态的两个部分明确，例如通过将每个帐户与唯一关联起来 Int ID。
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
8
2018-04-06 19:50
答案:
Scheme代码偷偷地使用两位状态：一个是变量之间的（隐式）关联 w1 和 w2 和ref-cell;另一个是存储在ref-cell中的（显式）状态。在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]
另一种选择是使状态的两个部分明确，例如通过将每个帐户与唯一关联起来 Int ID。
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
8
2018-04-06 19:50
好吧，你在这里有多个独立的，可变的状态：一个用于系统中的每个“帐户”。该 State monad只允许你拥有 一 一块国家。你可以存储类似的东西 (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 你应该得到你想要的清单。该 ST monad很简单：你可以创建和修改 STRefs，就像常规的可变变量一样;实际上，它们的界面基本上与之相同 IORef秒。
唯一棘手的是额外的 s type参数，简称 国家线程。这用于关联每个 STRef 随着 ST 它创建的上下文。如果你可以返回一个，那将是非常糟糕的 STRef 从一个 ST 行动，并把它带到 另一个 ST 背景 - 整个观点 ST 是你可以在纯粹的代码之外运行它 IO，但如果 STRefs可以逃脱，你可以在monadic环境之外有一个不纯的，可变的状态，只需将你的所有操作都包裹起来 runST！所以，每一个 ST 和 STRef 携带相同的 s 类型参数，和 runST 有类型 runST :: (forall s. ST s a) -> a。这会阻止您选择任何特定值 s：您的代码必须使用所有可能的值 s。它从未被分配任何特定类型;仅用作保持状态线程隔离的技巧。
4
2018-04-06 19:49