Combinativo applicativo vs monadico e monad in Scalaz

Question

Un paio di settimane fa Dragisa Krsmanovic ha chiesto a question here su come utilizzare la monade gratuita in Scalaz 7 per evitare overflow dello stack in questa situazione (ho adattato un po 'il suo codice):

import scalaz._, Scalaz._ 

def setS(i: Int): State[List[Int], Unit] = modify(i :: _) 

val s = (1 to 100000).foldLeft(state[List[Int], Unit](())) { 
    case (st, i) => st.flatMap(_ => setS(i)) 
} 

s(Nil) 

ho pensato that just lifting a trampoline into StateT dovrebbe funzionare:

import Free.Trampoline 

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) { 
    case (st, i) => st.flatMap(_ => setS(i).lift[Trampoline]) 
} 

s(Nil).run 

Ma soffia ancora lo stack, quindi ho solo postato come commento.

Dave Stevens solo pointed out che sequenziamento con l'applicativo *> invece della monade flatMap in realtà funziona bene:

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) { 
    case (st, i) => st *> setS(i).lift[Trampoline] 
} 

s(Nil).run 

(Beh, è ​​super slow, naturalmente, perché questo è il prezzo da pagare per fare qualcosa di interessante come questo in Scala, ma almeno non c'è overflow dello stack.)

Cosa sta succedendo qui? Non penso che ci possa essere una ragione di principio per questa differenza, ma in realtà non ho idea di cosa potrebbe accadere nell'implementazione e non ho il tempo di scavare intorno al momento. Ma sono curioso e sarebbe bello se lo sapesse qualcun altro.

Answer 1

C'è un'intuizione basata sul principio per questa differenza.

L'operatore applicativo *> valuta l'argomento a sinistra solo per i suoi effetti collaterali e sempre ignora il risultato. Questo è simile (in alcuni casi equivalente) alla funzione >> di Haskell per le monadi. Ecco la sorgente per *>:

/** Combine `self` and `fb` according to `Apply[F]` with a function that discards the `A`s */ 
final def *>[B](fb: F[B]): F[B] = F.apply2(self,fb)((_,b) => b) 

e Apply#apply2:

def apply2[A, B, C](fa: => F[A], fb: => F[B])(f: (A, B) => C): F[C] = 
    ap(fb)(map(fa)(f.curried)) 

In generale, flatMap dipende dal risultato dell'argomento sinistra (deve, in quanto è l'ingresso alla funzione a destra discussione). Anche se in questo caso specifico stai ignorando il risultato sinistro, flatMap non lo sa.

Sembra probabile, dati i risultati, che l'implementazione per *> sia ottimizzata per il caso in cui il risultato dell'argomento a sinistra non è necessario. Tuttavia, flatMap non può eseguire questa ottimizzazione e quindi ogni chiamata aumenta lo stack mantenendo il risultato sinistro non utilizzato.

È possibile che questo possa essere ottimizzato a livello di compilatore (scalac) o JIT (HotSpot) (il GHC di Haskell esegue certamente questa ottimizzazione), ma per ora sembra un'opportunità di ottimizzazione mancata.

Answer 2

solo per aggiungere alla discussione ...

In StateT, si dispone:

def flatMap[S3, B](f: A => IndexedStateT[F, S2, S3, B])(implicit F: Bind[F]): IndexedStateT[F, S1, S3, B] = 
    IndexedStateT(s => F.bind(apply(s)) { 
    case (s1, a) => f(a)(s1) 
    }) 

Le correzioni apply(s) il riferimento stato attuale nello stato successivo.

bind definizione interpreta avidamente i suoi parametri cattura il riferimento perché richiede che:

def bind[A, B](fa: F[A])(f: A => F[B]): F[B] 

A differenza di ap che potrebbero non hanno bisogno di interpretare uno dei suoi parametri:

def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B] 

Con questa codice, il Trampoline non può aiutare per StateTflatMap (e anche map) ...

Answer 3

Il mandubico è corretto, la flatMap di StateT non consente di aggirare l'accumulo di stack a causa della creazione del nuovo StateT immediatamente prima di chiamare il binding del monad avvolto (che sarebbe una [Funzione0] libera nel tuo caso).

Quindi il trampolino non può essere di aiuto, ma la Monade libera sul funtore per Stato è un modo per garantire la sicurezza dello stack.

Vogliamo passare dallo stato [Elenco [Int], Unità] a Libero [a [Stato [Elenco [Int], a], Unità] e la nostra chiamata flatMap sarà sulla flatMap di Free (che non funziona altro che creare la struttura dati gratuita).

val s = (1 to 100000).foldLeft( 
    Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](state[List[Int], Unit](()))) { 
     case (st, i) => st.flatMap(_ => 
      Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](setS(i))) 
    } 

Ora abbiamo una struttura di dati incorporata libera che possiamo facilmente infilare uno Stato attraverso in quanto tale:

s.foldRun(List[Int]())((a,b) => b(a)) 

Calling liftF è abbastanza brutto quindi ho un PR per rendere più facile per Stato e le monadi Kleisli così speranzose in futuro non ci sarà bisogno di digitare lambda.

Edit: PR accettato così ora abbiamo

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).liftF) { 
     case (st, i) => st.flatMap(_ => setS(i).liftF) 
}