问题 管理国家 - 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很简单:你可以创建和修改 STRef
s,就像常规的可变变量一样;实际上,它们的界面基本上与之相同 IORef
秒。
唯一棘手的是额外的 s
type参数,简称 国家线程。这用于关联每个 STRef
随着 ST
它创建的上下文。如果你可以返回一个,那将是非常糟糕的 STRef
从一个 ST
行动,并把它带到 另一个 ST
背景 - 整个观点 ST
是你可以在纯粹的代码之外运行它 IO
,但如果 STRef
s可以逃脱,你可以在monadic环境之外有一个不纯的,可变的状态,只需将你的所有操作都包裹起来 runST
!所以,每一个 ST
和 STRef
携带相同的 s
类型参数,和 runST
有类型 runST :: (forall s. ST s a) -> a
。这会阻止您选择任何特定值 s
:您的代码必须使用所有可能的值 s
。它从未被分配任何特定类型;仅用作保持状态线程隔离的技巧。
4
2018-04-06 19:49