Использование состояния scalaz в более сложном вычислении
Я пытаюсь понять, как использовать scalaz State для выполнения сложного вычисления с учетом состояния. Вот проблема:
Учитывая List[Int] потенциальных делителей и a 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)]) }
^
Ответы
Ответ 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
Ответ 2
Я, наконец, понял это после долгих беспорядков:
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))
