[SOLVED] Monadic Reduce in the State Monad

Monadic Reduce in the State Monad

I'm stuck trying to reduce a list inside a state monad using a function returning State:

def op(t1: T, t2: T): State[S, T] 
val list: State[S, List[T]]

I'd like to reduce the list to get a State[S, T]

Solution

It's not possible to do this operation safely as written (what happens if the list is empty?), but if you have an identity element for op, you can use foldLeftM from Foldable:

list.flatMap(_.foldLeftM[({ type L[x] = State[S, x] })#L, T](opId)(op))

Alternatively you could write something like this:

list.flatMap {
  case h :: t => t.foldLeftM[({ type L[x] = State[S, x] })#L, T](h)(op)
  case Nil => ???
}

Unfortunately in both cases the type parameters are necessary (type inference won't work here), so you'd probably want to define a type alias and avoid the type lambda if you were doing much of this kind of thing.