Если я понимаю ваше требование
отложить все в flatMap и по-прежнему правильно указать общую стоимость
, тогда вы хотите вычислить оценку для общих затрат до выполнения каких-либо вычислений.Я не понимаю, как это должно работать с подписью flatMap[A](f: R => Calculation[A]): Calculation[A] - ваш cost привязан к Calculation[A], а ваш Calculation[A] зависит от конкретного экземпляра R, поэтому вы не можете вычислить стоимостьдо вычисления R.
Постоянные затраты на этапы вычисления
Вот совершенно другое предложение:
sealed trait Step[-A, +B] extends (A => B) { outer =>
def estimatedCosts: Int
def andThen[U >: B, C](next: Step[U, C]): Step[A, C] = new Step[A, C] {
def apply(a: A): C = next(outer(a))
def estimatedCosts = outer.estimatedCosts + next.estimatedCosts
}
def result(implicit u_is_a: Unit <:< A): B = this(u_is_a(()))
}
type Computation[+R] = Step[Unit, R]
Черта Step представляет вычислениешаг, для которого затраты не зависят от ввода.По сути это просто Function[A, B] с целочисленным значением.Тогда ваш Computation[R] становится особым случаем, а именно Step[Unit, R].
Вот как вы можете его использовать:
val x = new Step[Unit, Int] {
def apply(_u: Unit) = 42
def estimatedCosts = 0
}
val mul = new Step[Int, Int] {
def apply(i: Int) = {
println("<computing> adding is easy")
i + 58
}
def estimatedCosts = 10
}
val sqrt = new Step[Int, Double] {
def apply(i: Int) = {
println("<computing> finding square roots is difficult")
math.sqrt(i)
}
def estimatedCosts = 50
}
val c: Computation[Double] = x andThen mul andThen sqrt
println("Estimated costs: " + c.estimatedCosts)
println("(nothing computed so far)")
println(c.result)
Если вы запустите его, вы получите:
Estimated costs: 60
(nothing computed so far)
<computing> adding is easy
<computing> finding square roots is difficult
10.0
Что он делает следующим образом:
- Он начинается со значения
42, добавляет к нему 58, а затем вычисляет квадратный корень из суммы - Для сложения задана стоимость
10 единиц, квадратный корень стоит 50. - Он дает оценку стоимости
60 единиц без каких-либо вычислений. - Только когда выinvoke
.result вычисляет ли он фактический результат 10.0
По общему признанию, он не очень полезен ни для чего, кроме очень грубых оценок порядка величин.Это настолько грубо, что даже использование Int s едва ли имеет какой-либо смысл.
Непостоянные затраты за шаг
Вы можете сделать свои оценки затрат более точными, отслеживая размероцените следующим образом:
trait Step[-A, +B] extends (A => B) {
def outputSizeEstimate(inputSizeEstimate: Int): Int
def costs(inputSizeEstimate: Int): Int
}
trait Computation[+R] { outer =>
def result: R
def resultSize: Int
def estimatedCosts: Int
def map[S](step: Step[R, S]): Computation[S] = new Computation[S] {
def result: S = step(outer.result)
def estimatedCosts: Int = outer.estimatedCosts + step.costs(outer.resultSize)
def resultSize: Int = step.outputSizeEstimate(outer.resultSize)
}
}
val x = new Computation[List[Int]] {
def result = (0 to 10).toList
def resultSize = 10
def estimatedCosts = 10
}
val incrementEach = new Step[List[Int], List[Int]] {
def outputSizeEstimate(inputSize: Int) = inputSize
def apply(xs: List[Int]) = {
println("incrementing...")
xs.map(1.+)
}
def costs(inputSize: Int) = 3 * inputSize
}
val timesSelf = new Step[List[Int], List[(Int, Int)]] {
def outputSizeEstimate(n: Int) = n * n
def apply(xs: List[Int]) = {
println("^2...")
for (x <- xs; y <- xs) yield (x, y)
}
def costs(n: Int) = 5 * n * n
}
val addPairs = new Step[List[(Int, Int)], List[Int]] {
def outputSizeEstimate(n: Int) = n
def apply(xs: List[(Int, Int)]) = {
println("adding...")
xs.map{ case (a, b) => a + b }
}
def costs(n: Int) = 7 * n
}
val y = x map incrementEach map timesSelf map addPairs
println("Estimated costs (manually): " + (10 + 30 + 500 + 700))
println("Estimated costs (automatically): " + y.estimatedCosts)
println("(nothing computed so far)")
println(y.result)
Вывод выглядит обнадеживающим:
Estimated costs (manually): 1240
Estimated costs (automatically): 1240
(nothing computed so far)
incrementing...
^2...
adding...
List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...[omitted]..., 20, 21, 22)
Обратите внимание, что подход не ограничивается списками и целыми числами: оценки размера могут быть произвольно сложными.Например, они могут быть размерами матриц или тензоров.На самом деле, они вовсе не должны быть размеров .Эти оценки также могут содержать любые другие виды «статических консервативных оценок», такие как типы или логические предикаты.
Непостоянные затраты с использованием Writer
Использование Writer монаду от Cats, мы можем выразить ту же идею более кратко, заменив два метода outputSizeEstimate и costs на Step одним методом, который принимает Int и возвращает Writer[Int, Int]:
Writer с .value соответствует оценке размера для вывода Writer с .written соответствует стоимости шага (которая может зависеть от размера ввода)
Полный код:
import cats.data.Writer
import cats.syntax.writer._
import cats.instances.int._
object EstimatingCosts extends App {
type Costs = Int
type Size = Int
trait Step[-A, +B] extends (A => B) {
def sizeWithCosts(inputSizeEstimate: Size): Writer[Costs, Size]
}
object Step {
def apply[A, B]
(sizeCosts: Size => (Size, Costs))
(mapResult: A => B)
: Step[A, B] = new Step[A, B] {
def apply(a: A) = mapResult(a)
def sizeWithCosts(s: Size) = { val (s2, c) = sizeCosts(s); Writer(c, s2) }
}
}
trait Computation[+R] { outer =>
def result: R
def sizeWithCosts: Writer[Costs, Size]
def size: Size = sizeWithCosts.value
def costs: Costs = sizeWithCosts.written
def map[S](step: Step[R, S]): Computation[S] = new Computation[S] {
lazy val result: S = step(outer.result)
lazy val sizeWithCosts = outer.sizeWithCosts.flatMap(step.sizeWithCosts)
}
}
object Computation {
def apply[A](initialSize: Size, initialCosts: Costs)(a: => A) = {
new Computation[A] {
lazy val result = a
lazy val sizeWithCosts = Writer(initialCosts, initialSize)
}
}
}
val x = Computation(10, 10){ (0 to 10).toList }
val incrementEach = Step(n => (n, 3 * n)){ (xs: List[Int]) =>
println("incrementing...")
xs.map(1.+)
}
val timesSelf = Step(n => (n * n, 5 * n * n)) { (xs: List[Int]) =>
println("^2...")
for (x <- xs; y <- xs) yield (x, y)
}
val addPairs = Step(n => (n, 7 * n)) { (xs: List[(Int, Int)]) =>
println("adding...")
xs.map{ case (a, b) => a + b }
}
val y = x map incrementEach map timesSelf map addPairs
println("Estimated costs (manually): " + (10 + 30 + 500 + 700))
println("Estimated costs (automatically): " + y.costs)
println("(nothing computed so far)")
println(y.result)
}
Вывод остается точно таким же, как в предыдущем разделе.
PS: Я думаю, что придумалболее краткий способ суммировать весь этот ответ:
Используйте категорию продукта обычной внешней среды Scala (типы и функции) с моноидом эндоморфизмов на объекте Int в категории Клейсли Writer[Int, ?].
В какой-то гипотезеНеверный язык, ответ мог бы быть:
Использовать Sc * End{Kl(Writer[Int, ?])}[Int].