管理狀態 - SICP第3章

Question

我一直在Structure and Interpretation of Computer Programs中完成並完成Haskell中的練習。前兩章沒有問題（代碼爲github），但第3章讓我更加難以思考。

它首先討論管理狀態，以銀行賬戶爲例。他們通過

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

定義一個函數make-withdraw讓你可以執行以下代碼：

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

(w1 50) 
50 

(w2 70) 
30 

(w2 40) 
"Insufficient funds" 

(w1 40) 
10 

我不知道我怎麼能在Haskell模擬此。我首先想到的使用狀態單子一些簡單的功能：

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。有什麼建議？

Answer 1

該方案代碼是偷偷使用兩個狀態位：一個是（變量w1和w2之間的（隱式）關聯和一個ref-cell;另一個是存儲在ref-cell中的（顯式）狀態。在Haskell中有幾種不同的方法來模擬它。例如，我們可以拉一個類似裁判細胞招用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 
    } 

當然，我們便基本上可重新實現裁判電池操作：

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 

Answer 2

那麼，你有多個獨立的，可變的狀態在這裏：一個系統中的每個「帳戶」。該State單子只讓你有一個一塊狀態。你可以存儲類似(Int, Map Int Cash)的狀態，遞增Int每次取得一個新的鑰匙插入地圖，並用它來儲存的平衡......但是這是這麼難看，是不是？

然而，謝天謝地，Haskell有一個單獨的多個獨立的可變狀態片段：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類型參數，稱爲狀態線程。這是用來給每個STRef用它創建的ST的上下文關聯的這將是非常糟糕的，如果你可以從ST動作返回STRef，和對面另一個ST背景下攜帶 - 的ST整點就是你可以在IO之外將其作爲純代碼運行，但如果STRef可能會逃脫，則只需將所有操作包裝在runST之內，就可以在單子環境之外獲得不純的可變狀態！因此，每個ST和STRef都帶有相同的s類型參數，並且runST的類型爲runST :: (forall s. ST s a) -> a。這會阻止您爲s選擇任何特定值：您的代碼必須使用s的所有可能值。它從來沒有分配任何特定的類型;只是用來保持狀態線程孤立。