问题 管理国家 - 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



谢谢,这是一个很好的答案。 - Chris Taylor


答案:


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



谢谢,这是一个很好的答案。 - Chris Taylor


好吧,你在这里有多个独立的,可变的状态:一个用于系统中的每个“帐户”。该 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



谢谢,ST的解释真的很有帮助! - Chris Taylor