Standard way to combine States in scalaz

Question

Consider, you have the Nel of states (Nel stands for NonEmptyList, to make things shorter), and you want to combine the States to one State, using some function f, for left part of the state and g for the right part of the state.

So you want something like this:

def foldStatesG[S, A](in: NonEmptyList[State[S, A]])(f: (A, A) => A)(g: (S, S) => S): State[S, A] = {
    in.foldLeft1((s1, s2) => State(e => {
      val ss1 = s1(e)
      val ss2 = s2(e)
      g(ss1._1, ss2._1) -> f(ss1._2, ss2._2)
    }))
  }

I am sure, that I am inventing the bicycle, and such thing already exists, probably in a more general way. But, looking through scalaz I failed to find or recognize it. Would appreciate of any help on this topic.

The second question, describes how I came to such problem. I wanted to make a small simulation, when you have an Enemy (consider it's just a Double), and all possible spells which might hit him Nel[Spell]. So basically I want to generate all possible sequences. For example, if Nel[Spell] = ($, #), then given an enemy E, progression would look like

E -> (), then Nel(E -> $, E -> #), then Nel(E -> $$, E -> ##, E -> $#, E-> #$) etc.. (pseudo code)

Without going too much into details I need something like this:

def combineS(variations: NonEmptyList[Spell]): State[NonEmptyList[(Enemy, List[Spell])], Boolean]

In other words, you provide it with all possible moves, and it simulates all possible states. You can consider it as a kind of decision tree, which branches off every step. Hence I defined, how to proceed with one spell.

def combineS1(spell: Spell): State[(NonEmptyList[(Enemy, List[Spell])]), Boolean]
    // some logic

The problem is, that I can not implement it via simple traverse:

def combineS(variations: NonEmptyList[Spell]): State[NonEmptyList[(Enemy, List[Spell])], Boolean] = {
    val x = variations traverse combine1 // State[Nel[..], Nel[Boolean]
    x map { _.suml1(conjunction)}
}

Because in traverse, the Nels are not appended to each other, but discarded. That's why I came up with this solution:

  def combineS(variations: NonEmptyList[Spell]): State[NonEmptyList[(Enemy, List[Spell])], AllDead] = {
    val x: NonEmptyList[State[NonEmptyList[(Enemy, List[Spell])], Boolean]] = variations map combineS
    foldStates(x)(_ && _)(append)
  }

That code is actually working, but I feel like there's a way to traverse it, without additional foldState.

What would be other functional approaches to do such simulations (in terms of concepts at least). I can write it simply functional, without using high level concepts, but the purpose of this exercise was exactly to learn advanced stuff. (May be it is exactly the job for Writer Monad? or Comonad?)

Also, if stackoverflow is not the best place for such questions, please, point out, where such questions are supposed to be asked?

I think this is a good question for Stack Overflow—just haven't had a chance to answer. — Travis Brown

Hugh Hugh · Accepted Answer · 2015-05-05T06:51:14

Well, to answer the first part of that, if we were in an alternative universe where Scalaz already had a Biapplicative type class, we could use it as follows:

def foldStatesG[S, A](states: NonEmptyList[State[S, A]], s: (S, S) ⇒ S, a: (A, A) ⇒ A): State[S, A] =
  states.foldLeft1(IndexedStateT.indexedStateTBiapplicative[Id, S].bilift2(s, a))

But we don't, so we'd need something like the following (n.b. I haven't ensured this does anything sane law-wise):

trait Biapplicative[F[_, _]] extends Bifunctor[F] {
  def bipure[A, B](a: ⇒ A, b: ⇒ B): F[A, B]
  def biapply[A, B, C, D](fab: ⇒ F[A, B])(f: ⇒ F[A ⇒ C, B ⇒ D]): F[C, D]
  def bilift2[A, B, C, D, E, G](fab: (A, B) ⇒ C, fde: (D, E) ⇒ G): (F[A, D], F[B, E]) ⇒ F[C, G] =
    (fad: F[A, D], fbe: F[B, E]) ⇒
      biapply(fbe)(bimap[A, D, B ⇒ C, E ⇒ G](fad)(fab.curried, fde.curried))
}

object Biapplicative {
  implicit def indexedStateTBiapplicative[F[_], S1](implicit F: Applicative[F]) =
    new Biapplicative[IndexedStateT[F, S1, ?, ?]] {
      def bipure[A, B](a: ⇒ A, b: ⇒ B) =
        StateT.constantIndexedStateT(b)(a)
      def biapply[A, B, C, D]
          (fab: ⇒ IndexedStateT[F, S1, A, B])
          (f: ⇒ IndexedStateT[F, S1, A ⇒ C, B ⇒ D]) =
        new IndexedStateT[F, S1, C, D] {
          def apply(initial: S1): F[(C, D)] =
            F.ap(fab(initial))(F.map(f(initial)) {
              case (a2c, b2d) ⇒ Bifunctor[Tuple2].bimap(_)(a2c, b2d)
            })
        }
    }
}

Standard way to combine States in scalaz

1 Answers