Applicative vs. Monadic Combinators i bezpłatna monada w Scalaz

Question

Kilka tygodni temu Dragisa Krsmanovic zapytał a question here o to, jak korzystać z bezpłatnej monady w Scalaz 7, aby uniknąć przepełnienia stosu w tej sytuacji (trochę zaadaptowałem jego kod):

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) 

Myślałem that just lifting a trampoline into StateT powinno działać:

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 

Ale to wciąż wieje stos, więc po prostu pisał je jako komentarz.

Dave Stevens tylko pointed out że sekwencjonowanie z aplikacyjnej *> zamiast monadycznej flatMap faktycznie działa dobrze:

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

s(Nil).run 

(Cóż, to bardzo wolno, oczywiście, bo to cena, jaką płacą za to nic ciekawego jak to w Scali, ale przynajmniej nie ma przepełnienia stosu.)

Co tu się dzieje? Nie sądzę, aby istniała podstawowa przyczyna tej różnicy, ale tak naprawdę nie mam pojęcia, co może się dziać w tej implementacji i nie mam czasu, aby w tej chwili kopać. Ale jestem ciekawy i byłoby fajnie, gdyby ktoś inny wiedział.

Answer 1

Istnieje intuicyjna intuicja dla tej różnicy.

Operator aplikacyjny oblicza lewy argument tylko dla efektów ubocznych, a zawsze ignoruje wynik. Jest to podobne (w niektórych przypadkach równoważne) do funkcji Haskella dla monad. Oto źródło *>:

/** 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) 

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

Ogólnie flatMap zależy od wyniku lewego argumentu (to musi, jak to jest wejście do funkcji w prawo argument). Mimo że w tym konkretnym przypadku ignorujesz lewy wynik, flatMap tego nie wie.

Wydaje się prawdopodobne, biorąc pod uwagę twoje wyniki, że implementacja dla *> jest zoptymalizowana dla przypadku, gdy wynik lewego argumentu nie jest potrzebny. Jednak flatMap nie może wykonać tej optymalizacji, więc każde połączenie zwiększa stos, zachowując nieużywany wynik.

Możliwe, że można to zoptymalizować na poziomie kompilatora (skala) lub JIT (HotSpot) (Hashla GHC z pewnością wykonuje tę optymalizację), ale na razie wydaje się, że straciliśmy szansę na optymalizację.

Answer 2

Wystarczy dodać do dyskusji ...

W StateT, masz:

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

W apply(s) ustala prąd odniesienia państwa w następnym stanie.

bind definicja interpretuje skwapliwie jego parametry łapanie odniesienia, ponieważ wymaga go:

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

Przy różnicy ap który może nie trzeba interpretować jeden z jego parametrów:

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

Z tego kod, Trampoline nie może pomóc dla StateTflatMap (a także map) ...

Answer 3

Mandubian jest poprawny, flatMap of StateT nie pozwala ominąć akumulacji stosu z powodu utworzenia nowego StateT bezpośrednio przed wywołaniem wiązania zapakowanej monady (która byłaby Free [Function0] w twoim przypadku).

Tak więc trampolina nie może pomóc, ale wolna monada nad funktorem dla państwa jest jednym ze sposobów zapewnienia bezpieczeństwa stosu.

Chcemy przejść ze stanu [Lista [Int], Jednostka], aby uwolnić [a [Państwo [Lista [Int], a], Jednostka], a nasze wywołanie flatMap będzie na Mapę Płaskiego Free'a (to nie robi cokolwiek innego niż tworzenie struktury Free danych).

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

Teraz mamy darmowe struktura danych zbudowany, że możemy łatwo nawlec stanu poprzez jako takie:

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

Wywołanie liftF jest dość brzydki więc mam PR w celu ułatwienia państwa i monady Kleisli, więc miejmy nadzieję, że w przyszłości nie będzie trzeba pisać lambdas.

Edit: PR przyjął więc teraz mamy

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