使用cat执行递归monad

Question

有一个简单的抽象查找服务，可以通过关键字检索值：

trait LookUp[F[_]] {
def read(key: String): F[Option[String]]
}

这个服务有一个用例，其想法是给实现的存储和累加器提供起始键，然后如果结果为None，则从db中请求值，然后停止并返回None，如果找到了值，则将其添加到累加器列表中，并从上一个调用结果中查找下一个值作为键。当在检索之前已找到检索值或检索到None时，执行停止。然后返回一个包含所有acc元素的字符串作为结果。

尝试如下：

def readWhileFound[F[_]: Monad](db: LookUp[F], acc: List[String]): F[Option[String]] = {
for{ result <- db.read(acc.head)} yield result match {
case Some(value) if(!acc.contains(value)) => readWhileFound(db, value::acc)
case _ => acc.mkstring("")      
}
}

但我不能得到正确的类型得到不匹配的错误，如：

found   : F[cats.data.OptionT[[_]F[_],String]]
required: cats.data.OptionT[F,String]

进近2：

def readWhileFound[F[_]: Monad](key: String, db: LookUp[F])(implicit m: Monad[F]): F[Option[String]] = {
m.tailRecM((Option(key), List.empty[String])) { case (currentK, accum) =>
currentK match {
case Some(value) if(!accum.contains(value)) => m.pure(Left((db.read(value), value :: accum)))
case _        => m.pure(Right(Some(accum.mkString(""))))
}
}
}

获取编译器错误：

(Found)  F[Option[String]]
required: Option[String]
case Some(value) if(!accum.contains(value)) => m.pure(Left((db.read(value), value :: accum)))

看起来db.read(值(应该以某种方式从F 中展开

Answer 1

这看起来是fs2:的一个很好的用例

你应该能够做这样的事情：

import fs2.Stream
def readWhileFound[F[_]: Concurrent](db: LookUp[F])(initialKey: String): F[List[String] =
Stream.unfoldEval(initialKey) { currentKey =>
db.read(key = currentKey).map(k => (k, k))
}.compile.toList

Answer 2

您在第一个实现中使用了错误的表达式match。你应该在result上match，而不是为了理解而在整体上。下面的实现应该符合您的要求。

def readWhileFound[F[_]: Monad](db: LookUp[F], startKey: String): F[Option[String]] = {
def loop(currKey: String, seenKeys: Set[String]): F[Option[String]] = {
db.read(currKey).flatMap {
case Some(nextKey) if !seenKeys.contains(nextKey) =>
loop(nextKey, seenKeys + nextKey)
case _ if seenKeys.nonEmpty => seenKeys.mkString("").some.pure[F]
case _ => none[String].pure[F]
}
}
loop(startKey, Set.empty)
}

我已经用Set替换了List作为累加值，因为它的contains方法更有效，但如果您关心返回结果中的顺序，则必须返回到List(效率较低(或使用两个累加器(一个Set，另一个List(。