Quando usare la monade ST in Scala?

Question

Scalaz offre una bella astrazione su calcoli statali: la monade ST.

La monade ST consente di acquisire un calcolo di effetti collaterali in una forma funzionale.

In Haskell, suppongo, l'utilizzo di tale monade è l'unico modo per implementare in modo efficiente alcuni algoritmi imperativi.

Ma in Scala posso semplicemente usare strutture dati mutabili se necessario.

Quello che ho scoperto è che l'utilizzo di concetti funzionali di Scalaz comporta un sovraccarico computazionale. Vedi ad esempio this question. Quindi non sembra ragionevole passare da un'implementazione funzionale a un'implementazione funzionale usando la monade ST, se l'obiettivo desiderato è un aumento di efficienza.

Quello che sto chiedendo è quindi:

• Quando è ragionevole usare la monade ST?
• In quali situazioni l'hai usato e sembrava essere una buona scelta?

Answer 1

Come Don Stewart ha giustamente osservato, ti sembra di essere alla ricerca della monade ST e non la monade Stato. Quindi la mia risposta sarà su questo.

La monade ST viene utilizzata per consentire la mutabilità locale in Haskell, dove solitamente non è consentita la mutevolezza. Ad esempio, se si desidera scrivere una funzione imperativa sum, si utilizzerà la monade ST. Un esempio di tale funzione con scalaz sarebbe (tratto da here):

def sumST[S, A](as: List[A])(implicit A: Numeric[A]): ST[S, A] = 
    for { n <- newVar(A.zero) 
     _ <- as.traverseU(a => n.mod(A.plus(_, a))) 
     m <- n.read } yield m 

def sum[A : Numeric](as: List[A]): A = 
    runST(new Forall[({type λ[S] = ST[S, A]})#λ] { 
    def apply[S] = sumST[S, A](as) 
    }) 

Ovviamente in scala potremmo anche solo scrivere:

def sum[A](xs: List[A])(implicit N: Numeric[A]) = { 
    var sum = N.zero 
    val it = xs.iterator 
    while (it.hasNext) { 
    sum = N.plus(sum, it.next) 
    } 
    sum 
} 

Questo sarebbe ancora referenzialmente trasparente, come nessuna stato mutevole sfugge allo scopo della funzione. In Haskell è usato in questi casi, perché semplicemente non possiamo avere un var.

Quindi perché dovremmo usare ST in scala? Se vuoi lavorare su una struttura mutevole (come una matrice) e vuoi garantire che questa struttura mutevole non sfugga allo scopo del calcolo, ma prima deve essere trasformata in una soluzione immutabile, puoi usare ST. In scalaz hai il STArray per questi casi, che sarà trasformato in un ImmutableArray quando viene eseguito il monad ST. Un buon esempio di ciò è lo binary sort example in scalaz. Vale la pena leggere anche il blog article on ST monad da Rúnar Bjarnason.