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

11

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

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   ответа
8

один - (неявная) связь между переменнымиw1 а такжеw2 и ref-ячейка; другое (явное) состояние хранится в ячейке ref. Есть несколько разных способов смоделировать это в Haskell. Например, мы могли бы использовать аналогичный трюк с 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
Error: User Rate Limit Exceeded Chris Taylor
4

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

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

Error: User Rate Limit Exceeded Chris Taylor

Похожие вопросы