haskell - Estado de gestión: capítulo 3 del SICP

state state-monad

Question

He estado trabajando en Estructura e Interpretación de Programas de Computadora y completando los ejercicios en Haskell. Los dos primeros capítulos estaban bien (código en github ) pero el Capítulo 3 me está haciendo pensar más.

Comienza hablando de administrar el estado, con el ejemplo de una cuenta bancaria. Definen una función make-withdraw por

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

para que pueda ejecutar el siguiente código:

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

(w1 50)
50

(w2 70)
30

(w2 40)
"Insufficient funds"

(w1 40)
10

No estoy seguro de cómo puedo emular esto en Haskell. Primero pensé en una función simple usando la mónada de estado:

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)

que me permite ejecutar el código

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

pero eso hace algo diferente al código del esquema. Idealmente, podría ejecutar algo así como

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]

pero no estoy seguro de cómo escribir la función makeWithdraw . ¿Algún consejo?

Answer 1

Bueno, aquí tienes varias piezas de estado independiente y mutable: una para cada "cuenta" en el sistema. La mónada de State solo te permite tener una pieza de estado. Podrías almacenar algo como (Int, Map Int Cash) en el estado, incrementando el Int para obtener una nueva clave en el mapa cada vez, y usar eso para almacenar el saldo ... pero eso es muy feo, ¿no?

Afortunadamente, sin embargo, Haskell tiene una mónada para múltiples piezas de estado independiente y mutable: 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"

Con esto, su ejemplo de código debería funcionar bien; simplemente aplique runST y debería obtener la lista que desea. La mónada ST es bastante simple: puedes simplemente crear y modificar STRef s, que actúan como variables mutables regulares; de hecho, su interfaz es básicamente idéntica a la de IORef s.

El único truco es el parámetro de tipo extra s , denominado subproceso de estado . Esto se usa para asociar cada STRef con el contexto ST en el que se ha creado. Sería muy malo si pudieras devolver un STRef de una acción ST y llevarlo a otro contexto ST : todo el punto de ST es que puedes ejecutar como código puro, fuera de IO , pero si los STRef pudieran escapar, tendrías un estado impuro y mutable fuera del contexto monádico, ¡simplemente envolviendo todas tus operaciones en runST ! Entonces, cada ST y STRef llevan el mismo parámetro de tipo s , y runST tiene el tipo runST :: (forall s. ST sa) -> a . Esto le impide elegir cualquier valor particular para s : su código tiene que funcionar con todos los valores posibles de s . Nunca se le asigna ningún tipo en particular; solo usado como un truco para mantener aislados los hilos de estado.

Answer 2

El código del Esquema es astuto usando dos bits de estado: uno es la asociación (implícita) entre las variables w1 y w2 y una célula ref; el otro es el estado (explícito) almacenado en una célula ref. Hay un par de maneras diferentes de modelar esto en Haskell. Por ejemplo, podríamos sacar un truco similar de ref-cell con 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'')

Lo que nos permite hacer esto:

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

Otra opción es hacer que ambas partes del estado sean explícitas, por ejemplo, asociando cada cuenta con una identificación única de Int .

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

Por supuesto, básicamente estaríamos reimplementando las operaciones de 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'')

Lo cual nos dejaría escribir makeWithdraw :

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