Scalaz: how to combine monads of type OptionT[State[_], T], so it won't terminate on None

Question

I am learning monad transformers and have a problem sequencing them

I created a type OptionTBitSetState[T]

I understand this type as a stateful computation that may fail

import scalaz._, Scalaz._
import scala.collection.immutable.BitSet

type BitSetState[T] = State[BitSet, T]
type OptionTBitSetState[T] = OptionT[BitSetState, T]
object OptionTBitSetState {
  def apply[T](option : Option[T]) : OptionT[BitSetState, T] =
    OptionT[BitSetState, T](State[BitSet, Option[T]](_ -> option))

  def apply[T](state : State[BitSet, T]) : OptionT[BitSetState, T] =
    OptionT[BitSetState, T](state.map(_.some))
}

I have a function step with signature

def step(i : Int) : OptionTBitSetState[Seq[Int]]

This function should:

1. Check if BitSet inside State contains parameter i
2. • If it does not contain: add i to BitSet and return Seq(i, i*10, i*100)
   • If it contains: fail with None

Implementation of function step:

def step(i : Int) : OptionTBitSetState[Seq[Int]] =
  for {
    usedIs <- OptionTBitSetState(get[BitSet])
    res <- OptionTBitSetState(
      Some(Seq(i, i*10, i*100)).filterNot(_ => usedIs.contains(i))
    )
    _ <- OptionTBitSetState(put(usedIs + i))
  } yield res

I want to sequence a list of steps in such way that when I evaluate this sequence, I get a list of options as a result. But signature of sequence is different. I get an option of lists instead.

e.g.

List(1,2,1,3).map(step).sequence.run(BitSet.empty)

returns None, but what I want is:

List(Some(Seq(1, 10, 100)), Some(Seq(2, 20, 200)), None, Some(Seq(3, 30, 300)))

Is there any way I can combine OptionTBitSetState[T]s, so I will get the behavior I need?

Answer 1

In my humble opinion, you are over-complicating the solution by using OptionT.

The problem with OptionT is that it wants to treat the value inside the monad as either existing or absent, so when you 'collapse' the individual computations into a single State to run it, any single failure must cause the entire thing to fail.

I would just use State[BitSet,Option[Seq[Int]]. Here's a (slightly modified for simplicity) Haskell version since I don't speak Scala particularly well.

module Main where

import Control.Monad.State
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import Data.Maybe (isJust)

step :: Int -> State IntSet (Maybe [Int])
step i = do
    set <- get
    if not (IntSet.member i set)
    then do
        modify $ IntSet.insert i
        return $ Just [i, i*10, i*100]
    else return Nothing

run xs = filter isJust $ flip evalState IntSet.empty $ mapM step xs

main = do
    let result = run [1,2,1,3]
    print result

What you really want is mapM or whatever Scala's equivalent is. Then just run the State action and remove the Nothing values.