Voici un morceau de code de la documentation de fs2 . La fonction go
est récursive. La question est de savoir comment savoir si elle est sans danger pour la pile et comment raisonner si une fonction est sans danger pour la pile?
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)
Serait-il également sûr de la pile si nous appelons go
d'une autre méthode?
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
Lev Denisov
la source
la source
go
pour utiliser, par exemple, uneMonad[F]
classe de types - il existe unetailRecM
méthode vous permettant d'exécuter le trampoline de manière explicite pour garantir que la fonction sera sécurisée. Je peux me tromper, mais sans cela, vous comptezF
être sûr de la pile (par exemple, s'il implémente le trampoline en interne), mais vous ne savez jamais qui définira votreF
, donc vous ne devriez pas faire cela. Si vous n'avez aucune garantie que laF
pile est sûre, utilisez une classe de type qui fournittailRecM
car elle est empilable par la loi.@tailrec
annotation pour les fonctions d'enregistrement de queue. Pour les autres cas, il n'y a aucune garantie formelle dans Scala AFAIK. Même si la fonction elle-même est sûre, les autres fonctions qu'elle appelle peuvent ne pas être: /.Réponses:
Ma réponse précédente donne ici des informations générales qui pourraient être utiles. L'idée de base est que certains types d'effets ont des
flatMap
implémentations qui prennent en charge directement la récursivité sans pile - vous pouvez imbriquer lesflatMap
appels explicitement ou par récursion aussi profondément que vous le souhaitez et vous ne déborderez pas la pile.Pour certains types d'effet, il n'est pas possible
flatMap
d'être compatible avec la pile, en raison de la sémantique de l'effet. Dans d'autres cas, il peut être possible d'écrire un coffre-fortflatMap
, mais les implémenteurs peuvent avoir décidé de ne pas le faire en raison des performances ou d'autres considérations.Malheureusement, il n'y a pas de moyen standard (ou même conventionnel) de savoir si
flatMap
pour un type donné est empilable. Les chats incluent unetailRecM
opération qui devrait fournir une récursion monadique empilable pour tout type d'effet monadique licite, et parfois regarder unetailRecM
implémentation qui est connue pour être licite peut fournir des indices sur si unflatMap
est empilable. Dans le cas,Pull
cela ressemble à ceci :tailRecM
C'est juste récursion parflatMap
, et nous savons quePull
« deMonad
l'instance est légitime , ce qui est assez bonne preuve quePull
l »flatMap
est - pile de sécurité. Le facteur de complication est ici que l'instance pourPull
a uneApplicativeError
contrainteF
quiPull
est leflatMap
fait pas, mais dans ce cas ne rien de changement.Donc l'
tk
implémentation ici est stack-safe carflatMap
onPull
est stack-safe, et nous le savons en regardant sontailRecM
implémentation. (Si nous creusions un peu plus profondément, nous pourrions comprendre queflatMap
c'est empilable carPull
c'est essentiellement un wrapper pourFreeC
, qui est trampoliné .)Il ne serait probablement pas très difficile de réécrire
tk
en termes detailRecM
, bien que nous devions ajouter laApplicativeError
contrainte autrement inutile . Je suppose que les auteurs de la documentation ont choisi de ne pas le faire par souci de clarté, et parce qu'ils savaientPull
que tout allaitflatMap
bien.Mise à jour: voici une
tailRecM
traduction assez mécanique :Notez qu'il n'y a pas de récursivité explicite.
La réponse à votre deuxième question dépend de ce à quoi ressemble l'autre méthode, mais dans le cas de votre exemple spécifique,
>>
il en résultera simplement plus deflatMap
couches, donc ça devrait aller.Pour répondre à votre question de manière plus générale, tout ce sujet est un désordre déroutant à Scala. Vous ne devriez pas avoir à fouiller dans les implémentations comme nous l'avons fait ci-dessus juste pour savoir si un type prend en charge ou non la récursion monadique empilable. De meilleures conventions autour de la documentation seraient une aide ici, mais malheureusement nous ne faisons pas un très bon travail. Vous pouvez toujours utiliser
tailRecM
pour être «sûr» (c'est ce que vous voudrez faire quand leF[_]
est générique, de toute façon), mais même alors, vous êtes confiant que l'Monad
implémentation est légale.Pour résumer: c'est une mauvaise situation tout autour, et dans des situations sensibles, vous devez absolument écrire vos propres tests pour vérifier que les implémentations comme celle-ci sont compatibles avec la pile.
la source
go
d'une autre méthode, qu'est-ce qui peut rendre la pile dangereuse? Si nous faisons des calculs non récursifs avant d'appeler,Pull.output(hd) >> go(tl, n - m)
ça va?ContT
l »flatMap
est en fait pile de sécurité (via uneDefer
contrainte sur le type sous - jacent). Je pensais plutôt à quelque chose commeList
, où la récurrenceflatMap
n'est pas empilable (elle a cependant un caractère légaltailRecM
).