在更复杂的计算中使用scalaz状态

Question

我试图了解如何使用scalaz State执行复杂的有状态计算.这是问题所在:

给定一个List[Int]潜在的除数和一个List[Int]数字,找到一个List[(Int, Int)匹配对(除数,数字),其中允许除数最多匹配一个数.

作为测试:

def findMatches(divs: List[Int], nums: List[Int]): List[(Int, Int)]

并通过以下输入:

findMatches( List(2, 3, 4), List(1, 6, 7, 8, 9) )

我们最多可以获得3场比赛.如果我们规定必须按照遍历列表lr的顺序进行匹配,那么匹配必须是:

List( (2, 6) ,  (3, 9) , (4, 8) )

所以需要通过以下两个测试:

assert(findMatches(List(2, 3, 4), List(1, 6, 7, 8, 9)) == List((2, 6), (3, 9), (4, 8)))
assert(findMatches(List(2, 3, 4), List(1, 6, 7, 8, 11)) == List((2, 6),  (4, 8)))

这是一个迫切的解决方案:

scala> def findMatches(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     |   var matches = List.empty[(Int, Int)]
     |   var remaining = nums
     |   divs foreach { div =>
     |     remaining find (_ % div == 0) foreach { n => 
     |       remaining = remaining filterNot (_ ==  n)
     |       matches = matches ::: List(div -> n) 
     |     }
     |   }
     |   matches
     | }
findMatches: (divs: List[Int], nums: List[Int])List[(Int, Int)]

请注意,我必须更新状态remaining以及累积matches.这听起来像scalaz遍历的工作!

我无用的工作让我走到了这一步:

scala> def findMatches(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     | divs.traverse[({type l[a] = State[List[Int], a]})#l, Int]( div =>
     | state { (rem: List[Int]) => rem.find(_ % div == 0).map(n => rem.filterNot(_ == n) -> List(div -> n)).getOrElse(rem -> List.empty[(Int, Int)]) }
     | ) ~> nums
     | }
<console>:15: error: type mismatch;
 found   : List[(Int, Int)]
 required: Int
       state { (rem: List[Int]) => rem.find(_ % div == 0).map(n => rem.filterNot(_ == n) -> List(div -> n)).getOrElse(rem -> List.empty[(Int, Int)]) }
                                                                                                                                       ^

Answer 1

您的代码只需稍加修改即可使用State和Traverse:

// using scalaz-seven
import scalaz._
import Scalaz._

def findMatches(divs: List[Int], nums: List[Int]) = {

  // the "state" we carry when traversing
  case class S(matches: List[(Int, Int)], remaining: List[Int])

  // initially there are no found pairs and a full list of nums
  val initialState = S(List[(Int, Int)](), nums)

  // a function to find a pair (div, num) given the current "state"
  // we return a state transition that modifies the state
  def find(div: Int) = modify((s: S) => 
    s.remaining.find(_ % div == 0).map { (n: Int) => 
      S(s.matches :+ div -> n, s.remaining -n)
    }.getOrElse(s))

  // the traversal, with no type annotation thanks to Scalaz7
  // Note that we use `exec` to get the final state
  // instead of `eval` that would just give us a List[Unit].
  divs.traverseS(find).exec(initialState).matches
}

// List((2,6), (3,9), (4,8))
findMatches(List(2, 3, 4), List(1, 6, 7, 8, 9))

您还可以使用不同的runTraverseS方式编写遍历:

 divs.runTraverseS(initialState)(find)._2.matches