Recursive monad execution with cats-CodePudding

There is simple abstract look up service with possibility to retrieve value by key:

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

There is use case of this service, idea is to give implemented storage and accumulator with starting key, then ask for value from db if the result is None then stop and Return None, if the value is found then add it to accumulator list and look up for next value as key from previous call result. Execution stops when retrieved value already is found before or None is retrieved. Then a string of all acc elements is returned as result.

Tried like this:

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

But I'm not able to get types right getting mismatch errors like:

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

Approach number 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(""))))
    }
  }
}

Getting compiler error:

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

Looks like db.read(value) somehow should be unwrapped out of F

CodePudding user response：

This looks like a great use case for fs2:

You should be able to do something like this:

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

CodePudding user response：

You are match-ing on the wrong expression in your first implementation. You should match on result, not on the entire for-comprehension. The implementation below should do what you're after.

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

I've replaced List with Set for the accumulated values because its contains method is more efficient, but if you care about the order in the returned result then you'll have to either go back to List (less efficient) or use two accumulators (one Set, the other List).