I've got functions with following signatures:
case class Sth(index: Long, str: String)
def fetch(n: Long): F[Sth] = ??? //implemented
def findFirstAndLast(min: Long, max: Long, str: String): F[(Long, Long)] = ???
I have certainty that str are grouped and groups don't occur twice.
For example this will be correct:
Sth(1, "a")
Sth(2, "a")
Sth(3, "b")
Sth(4, "b")
Sth(5, "b")
Sth(6, "c")
Sth(7, "d")
Sth(8, "d")
and that should be result of my function: findFirstAndLast(1, 8, "b") = F((3, 5))
But following case will never happen:
Sth(1, "a")
Sth(2, "b")
Sth(3, "b")
Sth(4, "a")
I tried to implement this but my brain stopped functioning when I've added the effect.
CodePudding user response：
Start by envisioning your algorithm as a recursive one, where there is some initial "state", and the algorithm can choose at each step to either update the state and recurse, or finish with a result.
You could represent your state as
case class State(index: Long, firstMatch: Option[Long])
where the index is the current index you are about to inspect, and the firstMatch is the index where you found your first matching string.
At each step, the algorithm will look at the index and check whether it is in-bounds compared to the max. If it's out of bounds, it must exit with whatever values it found. If it's in-bounds, grab the string associated with that index, then based on whether that string matches and whether you already found your firstMatch, decide whether to continue checking at the next index or return a result.
In order to perform recursion with effects, you're going to need a Monad[F]. You can find a lot of articles that explain what a Monad is, but to simplify for the purposes of this answer, it's a thing that knows how to flatMap your F, and provides the handy tailRecM function for doing that flatMapping recursively.
tailRecM is a way to represent a recursive algorithm with an F[_] effect.
def tailRecM[A, B](a: A)(f: (A) ⇒ F[Either[A, B]]): F[B]
The a: A is your initial state, e.g. State(min, None)
The f: A => F[Either[A, B]] is a function that inspects your current state, then decides whether to recurse, where that decision is done inside an F effect. Basically Left means recurse, Right means exit. It's perfect for your situation, where you have a fetch method that forces you into an F effect.
It returns an F[B] when your f returns an F[Right[B]], i.e. the end of recursion.
When you write your method, you just have to make sure there is a Monad available for the F type you're using, so you can use it to call tailRecM. In my demo, I put F as a type parameter on the method and made fetch into an argument, but I suspect in your code, both findFirstAndLast and fetch are defined inside some class that has the F type parameter. Adjust as necessary.
def findFirstAndLast[F[_]: Monad](
min: Long,
max: Long,
str: String,
fetch: Long => F[String],
)(implicit F: Monad[F]): F[Option[(Long, Long)]] =
F.tailRecM(State(min, None)) {
// if out of bounds, result is None if firstIndex was never found,
// or `firstIndex -> max` if it was found
case State(index, firstIndex) if index > max =>
// note: `f` wants an `F[Either[..]]` so we wrap the either with `F.pure`
F.pure(Right(firstIndex.map(_ -> max)))
// if in-bounds, fetch the index and decide from there
case State(index, firstMatch) =>
F.map(fetch(index)) {
case `str` if firstMatch.isEmpty =>
// found the first match!
Left(State(index 1, Some(index)))
case `str` if firstMatch.isDefined =>
// still matching after first
Left(State(index 1, firstMatch))
case other if firstMatch.isDefined =>
// no longer matching, last match must be previous step
Right(Some((firstMatch.get, index - 1)))
case other =>
// still looking for first match
Left(State(index 1, None))
}
}
Example usage with F=SyncIO, but this will work generally with any F type that has a Monad, e.g. IO, monix.eval.Task, Future, Option, etc.
def exampleFetch(n: Long) = SyncIO { "aabbbcdd".charAt(n.toInt - 1).toString }
val result = findFirstAndLast(1, 8, "b", exampleFetch).unsafeRunSync()
println(result) // Some((3, 5))