[scala] Scala Cats / fs2에서 스택 안전에 대해 추론하는 방법은 무엇입니까?

Program / 글쓴이

다음은 fs2 설명서의 일부 코드입니다 . 이 함수 go는 재귀 적입니다. 문제는 스택 안전인지 어떻게 알 수 있으며 어떤 함수가 스택 안전인지 판단하는 방법입니다.

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)

go다른 방법으로 호출하면 스택 안전 합니까?

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
}

답변

내 이전의 대답은 여기에 도움이 될 수있는 몇 가지 배경 정보를 제공합니다. 기본 아이디어는 일부 효과 유형에 flatMap스택 안전 재귀를 직접 지원하는 구현이 있다는 flatMap것입니다. 명시 적으로 또는 재귀를 통해 원하는만큼 깊이 호출 을 중첩 할 수 있으며 스택에 오버플로가 발생하지 않습니다.

일부 효과 유형 flatMap의 경우 효과의 의미로 인해 스택 안전을 유지할 수 없습니다 . 다른 경우에는 스택 세이프를 작성하는 것이 가능할 수 flatMap있지만 구현자는 성능 또는 기타 고려 사항으로 인해하지 않기로 결정했을 수 있습니다.

불행히도 flatMap주어진 유형에 대한 스택 안전 여부를 알 수있는 표준 (또는 기존의) 방법 은 없습니다. Cats에는 tailRecM모든 합법적 인 모나 딕 효과 유형에 대해 스택 안전 모나 딕 재귀를 제공해야하는 작업 이 포함되며 , 때로는 tailRecM합법적 인 것으로 알려진 구현을 보면 flatMap스택이 안전한지 여부에 대한 힌트를 얻을 수 있습니다. 이 경우 Pull다음과 같습니다 .

def tailRecM[A, B](a: A)(f: A => Pull[F, O, Either[A, B]]) =
  f(a).flatMap {
    case Left(a)  => tailRecM(a)(f)
    case Right(b) => Pull.pure(b)
  }

이 tailRecM단지를 통해 재귀되고 flatMap, 우리는 알고 Pull의 Monad인스턴스가 합법적 이 꽤 좋은 증거이다, Pull의 ‘ flatMapIS 스택 안전가. 여기 요인을 복잡 하나는의 인스턴스가 있다는 것입니다 Pull가 ApplicativeError에 제약 F이 Pull의 flatMap하지 않습니다,하지만 변경 아무것도하지 않는이 경우이다.

그렇게 tk때문에 여기에 구현 스택 안전 flatMap에 Pull스택 안전, 우리는에서의보고 알고 tailRecM구현입니다. (우리는 더 깊은 조금 파고 경우 우리가 알아낼 수 flatMap있기 때문에 스택 – 안전 Pull본질적에 대한 래퍼입니다 FreeC되어, trampolined .)

아마 다시 작성하는 것은 매우 어렵지 않을 것입니다 tk측면에서 tailRecM우리는 그렇지 않으면 불필요한 추가해야 할 것입니다 있지만, ApplicativeError제약. 나는이 문서의 저자를 추측하고있어 명확성을 위해 그렇게하지 않기로하고, 그들이 알고 있기 때문에 Pull‘이야 flatMap괜찮습니다.

업데이트 : 다음은 상당히 기계적인 tailRecM번역입니다.

import cats.ApplicativeError
import fs2._

def tk[F[_], O](n: Long)(implicit F: ApplicativeError[F, Throwable]): Pipe[F, O, O] =
  in => Pull.syncInstance[F, O].tailRecM((in, n)) {
    case (s, n) => s.pull.uncons.flatMap {
      case Some((hd, tl)) =>
        hd.size match {
          case m if m <= n => Pull.output(hd).as(Left((tl, n - m)))
          case m => Pull.output(hd.take(n.toInt)).as(Right(()))
        }
      case None => Pull.pure(Right(()))
    }
  }.stream

명시적인 재귀는 없습니다.

두 번째 질문에 대한 대답은 다른 방법의 모양에 따라 다르지만 특정 예제의 경우 >>더 많은 flatMap레이어가 생성되므로 괜찮을 것입니다.

더 일반적으로 귀하의 질문을 해결하기 위해이 전체 주제는 스칼라에서 혼란스러운 혼란입니다. 타입이 스택 세이프 모나드 재귀를 지원하는지 아닌지를 알기 위해 위에서 한 것처럼 구현을 파헤칠 필요가 없습니다. 문서에 관한 더 나은 규칙은 여기에 도움이 될 것입니다. 그러나 불행히도 우리는 그 일을 잘하지 않습니다. 당신은 항상 tailRecM“안전한”( F[_]어쨌든 일반적 일 때하고 싶은 것)로 사용할 수 있지만, 심지어 Monad구현이 합법적이라고 믿습니다.

요약하면 : 그것은 주위의 나쁜 상황이며 민감한 상황에서는 이와 같은 구현이 스택 안전인지 확인하기 위해 자체 테스트를 작성해야합니다.

답변