Verwaltungsstatus - Kapitel 3 von SICP

Question

Ich habe in Structure and Interpretation of Computer Programs gearbeitet und die Übungen in Haskell abgeschlossen. Die ersten beiden Kapitel waren in Ordnung (Code github), aber Kapitel 3 lässt mich härter denken.

Es beginnt mit der Verwaltung von Staat, am Beispiel eines Bankkontos. Sie definieren eine Funktion make-withdraw von

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

, so dass Sie den folgenden Code ausführen:

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

(w1 50) 
50 

(w2 70) 
30 

(w2 40) 
"Insufficient funds" 

(w1 40) 
10 

Ich bin nicht sicher, wie ich das in Haskell emulieren kann. Ich dachte zuerst an ein paar einfache Funktion der Staat Monade mit:

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) 

, die mir den Code

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

aber das macht etwas anderes Schema Code laufen zu lassen. Im Idealfall würde ich in der Lage sein, so etwas wie

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] 

laufen, aber ich bin nicht sicher, wie die Funktion makeWithdraw zu schreiben. Irgendein Rat?

Answer 1

Der Scheme-Code verwendet schleichend zwei Statusbits: Einer ist die (implizite) Assoziation zwischen den Variablen w1 und w2 und einer Ref-Zelle; der andere ist der (explizite) Zustand, der in einer Ref-Zelle gespeichert ist. Es gibt ein paar verschiedene Möglichkeiten, dies in Haskell zu modellieren.

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

Was uns auf diese Weise kann tun: Zum Beispiel könnten wir einen ähnlichen ref-Zelle Trick mit ST ziehen

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

Eine weiteren Option beiden Teile des Staates deutlich zu machen ist, zum Beispiel durch Zuordnen jedes einzelnen Accounts zu einer eindeutigen Int ID.

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

Natürlich würden wir dann im Grunde werden erneut die Umsetzung der ref-Zell-Operationen:

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

Was uns makeWithdraw dann lassen würde schreiben:

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

Answer 2

Nun, Sie haben mehrere Stücke von unabhängigen, veränderlichen Zustand hier: eine für jedes "Konto" im System. Die State Monade können Sie nur haben ein Stück Staat. Du könntest etwas wie (Int, Map Int Cash) in dem Zustand speichern und die Int inkrementieren, um jedes Mal einen neuen Schlüssel in die Karte zu bekommen und das zum Speichern des Guthabens zu verwenden ... aber das ist so hässlich, oder?

Glücklicherweise hat Haskell jedoch eine Monade für mehrere unabhängige, veränderbare Zustände: 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" 

Damit sollte Ihr Codebeispiel funktionieren; wenden Sie einfach runST an und Sie sollten die gewünschte Liste erhalten. Die ST Monade ist ziemlich einfach: Sie können einfach erstellen und ändern STRef s, die wie reguläre veränderbare Variablen handeln; Tatsächlich ist ihre Schnittstelle im Wesentlichen identisch mit der von IORef s.

Das einzige knifflige Bit ist der zusätzliche s-Typ-Parameter, der als -Status-Thread bezeichnet wird. Dies wird verwendet, um jede STRef mit dem ST Kontext zu assoziieren es in erstellt wird Es wäre sehr schlecht, wenn man eine STRef von einer ST Aktion zurückkehren konnte, und tragen sie über zu anderenST Kontext -. Der ganze Sinn ST ist, dass Sie kann es als reiner Code außerhalb von IO laufen lassen, aber wenn die STRef s entkommen könnte, hätten Sie einen unreinen, veränderlichen Zustand außerhalb des monadischen Kontextes, indem Sie einfach alle Ihre Operationen in runST verpacken! So trägt jeder ST und STRef ungefähr den gleichen s Typ Parameter, und runST hat den Typ runST :: (forall s. ST s a) -> a. Das hält Sie davon ab, einen bestimmten Wert für s zu wählen: Ihr Code muss mit allen möglichen Werten von s arbeiten. Es hat nie einen bestimmten Typ zugewiesen; nur als Trick verwendet, um die Status-Threads isoliert zu halten.