Oto fragment kodu z dokumentacji dla fs2 . Funkcja go
jest rekurencyjna. Pytanie brzmi: skąd wiemy, czy można je bezpiecznie nakładać i jak uzasadnić, czy jakakolwiek funkcja jest bezpieczna w stosie?
import fs2._
// import fs2._
def tk[F[_],O](n: Long): Pipe[F,O,O] = {
def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
s.pull.uncons.flatMap {
case Some((hd,tl)) =>
hd.size match {
case m if m <= n => Pull.output(hd) >> go(tl, n - m)
case m => Pull.output(hd.take(n.toInt)) >> Pull.done
}
case None => Pull.done
}
}
in => go(in,n).stream
}
// tk: [F[_], O](n: Long)fs2.Pipe[F,O,O]
Stream(1,2,3,4).through(tk(2)).toList
// res33: List[Int] = List(1, 2)
Czy byłoby również bezpieczne w stosie, gdybyśmy zadzwonili go
z innej metody?
def tk[F[_],O](n: Long): Pipe[F,O,O] = {
def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
s.pull.uncons.flatMap {
case Some((hd,tl)) =>
hd.size match {
case m if m <= n => otherMethod(...)
case m => Pull.output(hd.take(n.toInt)) >> Pull.done
}
case None => Pull.done
}
}
def otherMethod(...) = {
Pull.output(hd) >> go(tl, n - m)
}
in => go(in,n).stream
}
scala
functional-programming
tail-recursion
scala-cats
fs2
Lew Denisow
źródło
źródło
go
aby użyć np.Monad[F]
Klasy - istniejetailRecM
metoda umożliwiająca jawne wykonanie trampoliny, aby zagwarantować, że funkcja będzie bezpieczna w stosie. Mogę się mylić, ale bez tego polegasz naF
tym, że sam jesteś bezpieczny w stosie (np. Jeśli implementuje wewnętrznie trampolinę), ale nigdy nie wiesz, kto cię zdefiniujeF
, więc nie powinieneś tego robić. Jeśli nie masz żadnej gwarancji, żeF
jest bezpieczny w stosach, użyj klasy typu, która zapewnia,tailRecM
że zgodnie z prawem jest bezpieczny w stosach.@tailrec
adnotacji dotyczących funkcji nagrywania z tyłu. W innych przypadkach nie ma formalnych gwarancji w Scala AFAIK. Nawet jeśli sama funkcja jest bezpieczna, inne wywoływane funkcje mogą nie być: /.Odpowiedzi:
Moja poprzednia odpowiedź tutaj zawiera pewne podstawowe informacje, które mogą być przydatne. Podstawową ideą jest to, że niektóre typy efektów mają
flatMap
implementacje, które bezpośrednio obsługują rekurencję bezpieczną dla stosu - możesz zagnieżdżaćflatMap
połączenia jawnie lub poprzez rekurencję tak głęboko, jak chcesz, i nie przepełnisz stosu.W przypadku niektórych typów efektów nie jest możliwe
flatMap
zachowanie bezpiecznego stosu, ze względu na semantykę efektu. W innych przypadkach może być możliwe napisanie bezpiecznego dla stosuflatMap
, ale implementatorzy mogliby tego nie robić z powodu wydajności lub innych czynników.Niestety nie ma standardowego (ani nawet konwencjonalnego) sposobu na sprawdzenie, czy
flatMap
dany typ jest bezpieczny dla stosów. Koty zawierajątailRecM
operację, która powinna zapewnić bezpieczną dla stosu rekurencję monadyczną dla dowolnego zgodnego z prawem typu efektu monadycznego, a czasem spojrzenie natailRecM
implementację, o której wiadomo, że jest zgodna z prawem, może dostarczyć pewnych wskazówek na temat tego, czyflatMap
można bezpiecznie stosować stos. W przypadkuPull
wygląda na to, to :To
tailRecM
właśnie dzięki recursingflatMap
, i wiemy, żePull
jestMonad
instancja jest zgodne z prawem , co jest bardzo dobrym dowodem, żePull
'sflatMap
znaczy stos bezpieczny. Ten, komplikując czynnikiem jest to, że na przykładPull
maApplicativeError
ograniczenie naF
toPull
„sflatMap
nie, ale w tym przypadku to nie zmienia niczego.Tak więc
tk
implementacja jest bezpieczna dla stosu, ponieważflatMap
onPull
jest bezpieczny dla stosu, i wiemy to po spojrzeniu na jegotailRecM
implementację. (Jeśli wykopali głębiej możemy dowiedzieć się, żeflatMap
jest bezpieczny, ponieważ stosPull
jest zasadniczo otoki dlaFreeC
, których jest trampolined ).Prawdopodobnie nie byłoby strasznie trudne do przerobienia
tk
w kategoriachtailRecM
, choć musielibyśmy dodać inaczej niepotrzebneApplicativeError
ograniczenie. Zgaduję, że autorzy dokumentacji postanowili nie robić tego dla jasności, a ponieważ wiedzieliPull
, żeflatMap
jest w porządku.Aktualizacja: oto dość mechaniczne
tailRecM
tłumaczenie:Pamiętaj, że nie ma wyraźnej rekurencji.
Odpowiedź na twoje drugie pytanie zależy od tego, jak wygląda druga metoda, ale w przypadku twojego konkretnego przykładu,
>>
po prostu spowoduje więcejflatMap
warstw, więc powinno być dobrze.Aby odpowiedzieć bardziej ogólnie na twoje pytanie, cały ten temat jest mylącym bałaganem w Scali. Nie powinieneś zagłębiać się w implementacje, jak to zrobiliśmy powyżej, tylko po to, aby wiedzieć, czy typ obsługuje bezpieczną rekurencję monadyczną, czy nie. Pomocne byłyby lepsze konwencje dotyczące dokumentacji, ale niestety nie robimy tego zbyt dobrze. Zawsze możesz
tailRecM
być „bezpieczny” (coF[_]
zresztą chcesz zrobić, gdy jest to ogólne), ale nawet wtedy ufasz, żeMonad
wdrożenie jest zgodne z prawem.Podsumowując: ogólnie jest to zła sytuacja, aw delikatnych sytuacjach zdecydowanie powinieneś napisać własne testy, aby sprawdzić, czy takie implementacje są bezpieczne dla stosów.
źródło
go
z innej metody, co może sprawić, że będzie się ona niebezpiecznie nakładać? Jeśli wykonamy jakieś nierekurencyjne obliczenia, zanim zadzwonimy,Pull.output(hd) >> go(tl, n - m)
czy będzie w porządku?ContT
„sflatMap
jest rzeczywiście bezpieczny stos (poprzezDefer
ograniczenie o typie bazowym). Myślałem bardziej o czymś w rodzajuList
, w którym rekurencjaflatMap
nie jest bezpieczna dla stosów (choć jest zgodna z prawemtailRecM
).