Использование состояния скаляза в более сложных вычислениях - PullRequest
Новая
       32

Использование состояния скаляза в более сложных вычислениях

16 голосов
/ 08 февраля 2012

Я пытаюсь понять, как использовать 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 матча. Если мы оговариваем, что совпадения должны проводиться в том порядке, в котором они происходят при прохождении списков l-r, то совпадения должны быть: 

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. Звучит как работа для скараза!

Моя бесполезная работа зашла так далеко: 

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

Ответы [ 2 ]

16 голосов
/ 08 февраля 2012

Ваш код нужно только слегка изменить, чтобы использовать 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
1 голос
/ 08 февраля 2012

Я наконец-то понял это после долгих раздумий: 

scala> def findMatches(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     | (divs.traverse[({type l[a] = State[List[Int], a]})#l, Option[(Int, Int)]]( div =>
     |   state { (rem: List[Int]) => 
     |     rem.find(_ % div == 0).map(n => rem.filterNot(_ == n) -> Some(div -> n)).getOrElse(rem -> none[(Int, Int)]) 
     |   }
     | ) ! nums).flatten
     | }
findMatches: (divs: List[Int], nums: List[Int])List[(Int, Int)]

Думаю, я посмотрю на ответ Эрика, чтобы лучше понять, что на самом деле происходит.

<Ч />

Итерация # 2

Изучение ответа Эрика с использованием scalaz6 

scala> def findMatches2(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     |   case class S(matches: List[(Int, Int)], remaining: List[Int])
     |   val initialState = S(nil[(Int, Int)], nums)
     |   def find(div: Int, s: S) = {
     |     val newState = s.remaining.find(_ % div == 0).map { (n: Int) =>
     |       S(s.matches :+ div -> n, s.remaining filterNot (_ ==  n))
     |     }.getOrElse(s)
     |     newState -> newState.matches
     |   }
     |   val findDivs = (div: Int) => state((s: S) => find(div, s))
     |   (divs.traverse[({type l[a]=State[S, a]})#l, List[(Int, Int)]](findDivs) ! initialState).join
     | }
findMatches2: (divs: List[Int], nums: List[Int])List[(Int, Int)]

scala> findMatches2(List(2, 3, 4), List(1, 6, 7, 8, 9))
res11: List[(Int, Int)] = List((2,6), (2,6), (3,9), (2,6), (3,9), (4,8))

join на List[List[(Int, Int)]] в конце вызывает горе. Вместо этого мы можем заменить последнюю строку на: 

(divs.traverse[({type l[a]=State[S, a]})#l, List[(Int, Int)]](findDivs) ~> initialState).matches
<Ч />

Итерация # 3

Фактически, вы можете полностью исключить дополнительный вывод вычисления состояния и еще больше упростить: 

scala> def findMatches2(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     | case class S(matches: List[(Int, Int)], remaining: List[Int])
     | def find(div: Int, s: S) =
     |   s.remaining.find(_ % div == 0).map( n => S(s.matches :+ div -> n, s.remaining filterNot (_ ==  n)) ).getOrElse(s) -> ()
     | (divs.traverse[({type l[a]=State[S, a]})#l, Unit](div => state((s: S) => find(div, s))) ~> S(nil[(Int, Int)], nums)).matches
     | }
findMatches2: (divs: List[Int], nums: List[Int])List[(Int, Int)]

Итерация # 4

modify, описанный выше Apocalisp , также доступен в scalaz6 и избавляет от необходимости явно указывать пару (S, ()) (хотя вам нужно Unit в типе lambda): 

scala> def findMatches2(divs: List[Int], nums: List[Int]): List[(Int, Int)] = {
     | case class S(matches: List[(Int, Int)], remaining: List[Int])
     | def find(div: Int) = modify( (s: S) =>
     |   s.remaining.find(_ % div == 0).map( n => S(s.matches :+ div -> n, s.remaining filterNot (_ ==  n)) ).getOrElse(s))
     | (divs.traverse[({type l[a]=State[S, a]})#l, Unit](div => state(s => find(div)(s))) ~> S(nil, nums)).matches
     | }
findMatches2: (divs: List[Int], nums: List[Int])List[(Int, Int)]

scala> findMatches2(List(2, 3, 4), List(1, 6, 7, 8, 9))
res0: List[(Int, Int)] = List((2,6), (3,9), (4,8))
...