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

发布时间：2020-12-16 09:32:12 所属栏目：安全来源：网络整理

导读：我正在努力了解如何使用scalaz State执行复杂的有状态计算。这是问题： Given a List[Int] of potential divisors and a List[Int] of numbers,find a List[(Int,Int) ] of matching pairs (divisor,number) where a divisor is allowed to match at most on

我正在努力了解如何使用scalaz State执行复杂的有状态计算。这是问题：

Given a List[Int] of potential divisors and a List[Int] of numbers,find a List[(Int,Int)] of matching pairs (divisor,number) where a divisor is allowed to match at most one number.

作为测试：

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

并输入以下内容：

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

我们最多可以获得3场比赛。如果我们规定匹配必须按照它们通过列表l-r的顺序进行，那么匹配必须是：

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

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

assert(findMatches(List(2,9)) == List((2,8)))
assert(findMatches(List(2,11)) == List((2,8)))

这是一个迫在眉睫的解决方案：

scala> def findMatches(divs: 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)]

请注意，我必须更新剩余的状态以及累积的匹配。这听起来像是一个工作，

我无用的工作让我有这么远

scala> def findMatches(divs: 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)]) }
                                                                                                                                       ^

解决方法

您的代码只需要稍微修改才能使用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,8))
findMatches(List(2,9))

您也可以使用runTraverseS来写入遍历方式：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!