Управление государством-Глава 3 SICP

Я проработал в структуру и интерпретацию компьютерных программ и завершил упражнения в Хаскелле. Первые две главы были прекрасны (код на 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
Я не знаю, как я могу подражать этому в Хаскелле. Я первая мысль к некоторой простой функции, использующей монаду состояния: 
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. Какой-нибудь совет?

2 11
haskell sicp

2 ответа:

Код схемы исподтишка использует два бита состояния: один-это (неявная) ассоциация между переменными w1 и w2 и ref-ячейкой; другой-это (явное) состояние, хранящееся в ref-ячейке. Есть несколько различных способов смоделировать это в Хаскелле. Например, мы могли бы проделать подобный трюк с ref-ячейкой с 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.

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

Ну, у вас здесь есть несколько независимых, изменяемых состояний: по одному для каждого "счета" в системе. Монада State позволяет вам иметь только Один фрагмент состояния. Вы можете хранить что-то вроде (Int, Map Int Cash) в состоянии, увеличивая Int, чтобы каждый раз получать новый ключ в карту, и использовать его для хранения баланса... но ведь это так некрасиво, правда?

К счастью, однако, у Хаскелла есть монада для нескольких частей независимого, изменчивого состояния.: 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 довольно проста: вы можете просто создавать и изменять STRefs, которые действуют точно так же, как регулярные изменяемые переменные; на самом деле, их интерфейс в основном идентичен интерфейсу IORefs.

Единственным сложным битом является дополнительный параметр типа s, называемый потоком состояния . К этому привыкли свяжите каждый STRef с контекстом ST, в котором он создан. Было бы очень плохо, если бы вы могли вернуть STRef из действия ST и перенести его в другое действие . ST контекст-весь смысл ST заключается в том, что вы можете запустить его как чистый код, вне IO, но если бы STRefмогли убежать, у вас было бы нечистое, изменчивое состояние вне монадического контекста, просто обернув все ваши операции в runST! Таким образом, каждый ST и STRef несет примерно один и тот же параметр типа s, а runST имеет вид runST :: (forall s. ST s a) -> a. Это останавливает выбор любого конкретного значения для s: ваш код должен работать со всеми возможными значениями s. Он никогда не присваивается какому-либо определенному типу; просто используется как трюк, чтобы держать потоки состояний изолированными.
4