Gestión del estado - capítulo 3 de SICP

Question

He estado trabajando en Structure and Interpretation of Computer Programs 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 administración de 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 me puedo emular este en Haskell. Pensé por primera vez a una cierta función simple usando la mónada 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) 

sino que hace algo diferente al código de esquema. Idealmente me gustaría ser capaz de 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

El código del Esquema es sigilosamente utilizando dos bits de estado: uno es la asociación (implícita) entre las variables w1 y w2 y una celda 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 tirar de un truco de células ref similar 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') 

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 las dos piezas del estado explícita, por ejemplo, asociando cada cuenta con un ID único Int.

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

Por supuesto, tendríamos entonces, básicamente, se volverá a ejecutar las operaciones de células ref:

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') 

que luego escribamos makeWithdraw:

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

Answer 2

Bien, usted tiene varias piezas de estado independiente, mutable aquí: una para cada "cuenta" en el sistema. La mónada State solo le permite tener una pieza de estado. Puede guardar 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, 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; solo aplique runST y debería obtener la lista que desea. La mónada ST es bastante simple: puede 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 s adicional, denominado estado de la rosca. Esto se utiliza para asociar cada STRef con el contexto ST se crea en Sería muy malo si se puede devolver un STRef de una acción ST, y llevarlo a través de otraST contexto -. Todo el punto de ST es que se puede ejecutarlo como código puro, fuera de IO, pero si el STRef s pudiera escapar, tendría un estado impuro y mutable fuera del contexto monádico, simplemente envolviendo todas sus operaciones en runST! Por lo tanto, cada ST y STRef tiene el mismo parámetro de tipo s, y runST tiene el tipo runST :: (forall s. ST s a) -> 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.