Nhà nước quản lý - chương 3 của SICP

Question

Tôi đã làm việc qua số Structure and Interpretation of Computer Programs và hoàn thành các bài tập trong Haskell. Hai chương đầu tiên là tốt (mã số github) nhưng Chương 3 khiến tôi suy nghĩ nhiều hơn.

Bắt đầu bằng cách nói về quản lý trạng thái, với ví dụ về tài khoản ngân hàng. Họ định nghĩa một hàm make-withdraw bởi

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

để bạn có thể thực hiện đoạn mã sau:

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

(w1 50) 
50 

(w2 70) 
30 

(w2 40) 
"Insufficient funds" 

(w1 40) 
10 

Tôi không chắc chắn làm thế nào tôi có thể bắt chước này trong Haskell. đầu tiên tôi nghĩ đến một số chức năng đơn giản bằng cách sử dụng đơn nguyên nhà nước:

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) 

cho phép tôi để chạy mã

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

nhưng điều đó làm điều gì đó khác nhau để mã chương trình. Lý tưởng nhất là tôi có thể chạy một cái gì đó như

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] 

nhưng tôi không chắc chắn cách viết hàm makeWithdraw. Lời khuyên nào?

Answer 1

Mã lược đồ được sử dụng một cách lén lút sử dụng hai bit trạng thái: một là liên kết (ẩn) giữa các biến w1 và w2 và ô tái; khác là trạng thái (rõ ràng) được lưu trữ trong một ô ref. Có một vài cách khác nhau để mô hình hóa điều này trong Haskell. Ví dụ, chúng ta có thể kéo một thủ thuật ref cell tương tự với 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') 

nào cho phép chúng ta làm điều này:

*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] 

Một lựa chọn khác là làm cho cả hai miếng của nhà nước rõ ràng, ví dụ bằng cách liên kết từng tài khoản với một id Int duy nhất.

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

Tất nhiên, chúng tôi sẽ sau đó về cơ bản được tái triển khai các hoạt động 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') 

Mà sau đó sẽ cho phép chúng tôi viết makeWithdraw:

makeWithDraw :: Balance -> State BankState (Balance -> State BankState (Either String Balance)) 
makeWithdraw balance = withdraw <$> newAccount balance 

Answer 2

Vâng, bạn có nhiều phần trạng thái độc lập, có thể thay đổi tại đây: một cho mỗi "tài khoản" trong hệ thống. Đơn vị State chỉ cho phép bạn có một phần của trạng thái. Bạn có thể lưu trữ một cái gì đó như (Int, Map Int Cash) trong tiểu bang, tăng Int để nhận khóa mới vào bản đồ mỗi lần và sử dụng khóa đó để lưu trữ số dư ... nhưng điều đó thật xấu xí, phải không?

Rất may, Haskell có một đơn nguyên cho nhiều phần của trạng thái độc lập, có thể thay đổi: 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" 

Với điều này, ví dụ mã của bạn sẽ hoạt động tốt; chỉ cần áp dụng runST và bạn sẽ nhận được danh sách bạn muốn. Các đơn vị ST là khá đơn giản: bạn chỉ có thể tạo và sửa đổi STRef s, hoạt động giống như các biến có thể thay đổi thông thường; trên thực tế, giao diện của chúng về cơ bản giống với của IORef s.

Bit khó duy nhất là thông số loại bổ sung s, được gọi là chủ đề trạng thái . Này được sử dụng để kết hợp mỗi STRef với ST bối cảnh nó được tạo ra trong Nó sẽ là rất xấu nếu bạn có thể trả về một STRef từ một hành động ST, và mang nó trên để khác bối cảnhST -. Toàn bộ các điểm ST là bạn có thể chạy nó như mã thuần túy, bên ngoài IO, nhưng nếu STRef s có thể thoát ra, bạn có thể không tinh khiết, trạng thái có thể thay đổi bên ngoài ngữ cảnh đơn thuần, chỉ bằng cách gói tất cả các hoạt động của bạn trong runST! Vì vậy, mỗi ST và STRef mang cùng thông số loại s và runST có loại runST :: (forall s. ST s a) -> a. Điều này ngăn bạn chọn bất kỳ giá trị cụ thể nào cho s: mã của bạn phải hoạt động với tất cả các giá trị có thể có của s. Nó không bao giờ được gán bất kỳ loại cụ thể nào; chỉ được sử dụng như một thủ thuật để giữ cho các tiểu bang bị cô lập.