Scalaz：如何组合 OptionT[State[_], T] 类型的 monad，因此它不会在 None 上终止

Question

我正在学习 monad 转换器，但在排序时遇到问题

我创建了一个类型OptionTBitSetState[T]

我将此类型理解为可能会失败的状态计算

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

我有一个函数 step 带有签名

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

这个函数应该：

检查State里面的BitSet是否包含参数i
- 如果不包含：将i添加到BitSet和return Seq(i, i*10, i*100)
- 如果包含：失败 None

函数的实现步骤:

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

我想对步骤的列表进行排序，这样当我评估这个序列时，我会得到一个选项列表作为结果。但是 sequence 的签名不同。我得到了一个列表选项。

例如

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

returns None,但是我想要的是：

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

有什么方法可以组合 OptionTBitSetState[T]s，这样我就能得到我需要的行为吗？

Answer 1

以我的拙见，您使用 OptionT 使解决方案过于复杂。

OptionT 的问题在于它想将 monad 中的值视为存在或不存在，因此当您 'collapse' 将各个计算放入单个状态时运行它，任何一个故障都必须导致整个事情的失败。

我只会使用 State[BitSet,Option[Seq[Int]]。这是一个（为简单起见略作修改）Haskell 版本，因为我的 Scala 说得不是特别好。

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

你真正想要的是 mapM 或任何 Scala 的等价物。然后只需运行 State 操作并删除 Nothing 值。

Scalaz：如何组合 OptionT[State[_], T] 类型的 monad，因此它不会在 None 上终止

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

monads

scala

monad-transformers

scalaz