БЛОГ НА HUSL


Получение актуальных значений переменных в объекте-компаньоне абстрактного класса

Автор вопроса: nick

Необходимо реализовать неизменяемый стек через список на языке Scala, у которого в случае, если тип параметра является числовым, должна быть доступна операция average, возвращающая среднее арифметическое элементов стека и работающая за константное время.

Для реализации такого стека я создал абстрактный класс MegaStackAbs[T] и объект-компаньон для него (пока что только для одного из числовых типов Int, в дальнейшем легко обобщается на другие числовые типы).

abstract class MegaStackAbs[T](val values: List[T]) {
  val countedAverage: Double
  def average: Double
}

object MegaStackAbs {
  implicit object MegaStackInt extends MegaStackAbs[Int](???) {
    override val countedAverage: Double = values.sum.asInstanceOf[Double] / values.length
    
    override def average: Double = countedAverage
  }
}

В переменной values предполагается хранение элементов стека. В переменной countedAverage мной предполагается хранение заранее вычисленного среднего арифметического всех элементов стека, для того чтобы функция average возвращала данное вычисленное значение за константное время.

Затем я создал класс MegaStack[T], наследник абстрактного класса MegaStackAbs[T], в котором уже определил нужные мне стандартные операции для работы со стеком - push, pop, empty.

class MegaStack[T: MegaStackAbs](values: List[T]) extends MegaStackAbs[T](values) {
  override val countedAverage: Double = implicitly[MegaStackAbs[T]].countedAverage
  
  def push(value: T): MegaStack[T] = new MegaStack[T](values.appended(value))
  
  def pop: (MegaStack[T], T) = {
    if (empty) {
      throw new Exception("Stack is empty")
    }
    (new MegaStack[T](values.dropRight(1)), values.last)
  }
  
  def empty: Boolean = values.isEmpty
  
  override def average: Double = implicitly[MegaStackAbs[T]].average
  
  override def toString: String = values.toString()
}

Также я написал тесты на реализованный мной стек.

import org.scalatest.FunSuite

class MegaStackTest extends FunSuite {
  test("MegaStack[String]") {
    var stack = new MegaStack(List[String]("1", "2"))
    
    assert(!stack.empty)
    
    var result = stack.pop
    stack = result._1
    assert(result._2 == "2")
    assert(!stack.empty)
    
    stack = stack.push("3")
    assert(!stack.empty)
    
    result = stack.pop
    stack = result._1
    assert(result._2 == "3")
    assert(!stack.empty)
    
    result = stack.pop
    stack = result._1
    assert(result._2 == "1")
    assert(stack.empty)
  }
  test("MegaStack[Int]") {
    var stack = new MegaStack(List[Int](1, 2))
    
    assert(!stack.empty)
    assert(stack.average == 1.5)
    
    var result = stack.pop
    stack = result._1
    assert(result._2 == 2)
    assert(!stack.empty)
    assert(stack.average == 1)
    
    stack = stack.push(3)
    assert(!stack.empty)
    assert(stack.average == 2)
    
    result = stack.pop
    stack = result._1
    assert(result._2 == 3)
    assert(!stack.empty)
    assert(stack.average == 1)
    
    result = stack.pop
    stack = result._1
    assert(result._2 == 1)
    assert(stack.empty)
  }
}

Но при запуске тестов появляется две ошибки вида an implementation is missing, где первая появляется при объявлении стека в первом тесте, вторая при объявлении стека во втором тесте соответственно.

Подскажите, пожалуйста, что я сделал некорректно. Я полагаю, что ошибка в использовании ??? в объекте-компаньоне при передаче аргумента конструктору абстрактного класса. У меня совсем нет идей, как можно сделать так, чтобы среднее арифметическое всех элементов стека вычислялось заранее только для стеков с числовым типом параметра T и чтобы метод average был доступен только для них же. При помощи отладки моей программы я убедился, что переменная countedAverage в объекте-компаньоне вычисляется до того, как создаётся объект класса MegaStack[T]. Но тогда непонятно, как сделать так, чтобы в объекте-компаньоне получить доступ к актуальному значению переменной values объекта класса MegaStack[T], поскольку values в объекте-компаньоне будет равняться тому значению, которое я укажу вместо ??? при наследовании абстрактного класса MegaStackAbs[T]. Насколько мне известно, в Scala нельзя создать object с конструктором с аргументами, куда можно было бы передать актуальное значение переменной values.

P.S. Запрещено использовать ключевое слово var, поскольку необходимо придерживаться объектно-функциональной парадигмы в коде.


Источник

Ответы (1 шт):

Автор решения: Evgeny
  1. MegaStackAbs контейнер для чего? ??? просто бросает NotImplementedError при первом же вычислении к companion object MegaStackAbs
  2. T: MegaStackAbs означает что мы получаем implicit MegaStackAbs[T] у которого есть свои values[T] никак не связанные с текущим стеком и общие для все (так как implicit объект). И никак не связан с родителем MegaStackAbs

На самом деле самое простое - это если тип параметра является числовым, должна быть доступна операция average. Это означает что у нас должен быть метод расширения типа

implicit class  NumericStackWrapper[T: Numeric](stack: Stack[T]) {
  def average: T = ...
}

Считать average надо через implicitly[Numeric] но там нет ощего метода деления (так как у нас есть разделение на целые и дробные), соответственно надо два метода если мы хотим чтобы среднее было того же типа и задача была решена для общего случая. Получаем

implicit class NumericFraStack[T: Fractional](base: Stack[T]) {
  def average: T = {
    base match {
      case NumericStack(_, sum, count) =>
        val c = implicitly[Fractional[T]].fromInt(count)
        implicitly[Fractional[T]].div(sum, c)
      case _ =>
        throw new Exception("Wrong type")
    }
  }

implicit class NumericIntStack[T: Integral](base: Stack[T]) {
  def average: T = {
    base match {
      case NumericStack(_, sum, count) =>
        val c = implicitly[Integral[T]].fromInt(count)
        implicitly[Integral[T]].quot(sum, c)
      case _ =>
        throw new Exception("Wrong type")
    }
  }
}

Для целых мы берем целочисленное деление (.quot)

Далее нам надо где-то хранить частичный результат. Как видно из методов расширения, я думаю что лучше его хранить как два дополнительных поля в стеке - сумма элементов и количество элементов. Соответственно среднее вычисляется всегда за константное время и мы дополнительно не тратим время на переподсчет при добавлении и удалении элемента стека. Стек реализуем как trait и две приватные реализации:

sealed trait Stack[T] {
  def push(element: T): Stack[T]
  def pop(): (Stack[T], T)
}
object Stack {
  private[Stack] case class GeneralStack[T](elements: List[T]) extends Stack[T] {
    def push(element: T): GeneralStack[T] = {
      new GeneralStack[T](element :: elements)
    }

    def pop(): (GeneralStack[T], T) = elements match {
      case head :: tail =>
        new GeneralStack[T](tail) -> head
      case _ => throw new Exception("Stack is empty")
    }
  }

  private[Stack] case class NumericStack[T: Numeric] (elements: List[T], sum: T, count: Int) extends Stack[T] {
    def push(element: T): NumericStack[T] = {
      val newSum = implicitly[Numeric[T]].plus(sum, element)
      new NumericStack[T](element :: elements, newSum, count + 1)
    }

    def pop(): (NumericStack[T], T) = elements match {
      case head :: tail =>
        val newSum = implicitly[Numeric[T]].minus(sum, head)
        new NumericStack[T](tail, newSum, count - 1) -> head
      case _ => throw new Exception("Stack is empty")
    }
  }
}

Кстати стек нарастает спереди, добавлять и удалять элемент в конец - не эффективно

Теперь самое нетривиальное: Мы хотим чтобы у нас работало что-то вроде:

Stack.empty[Int].push(1).push(2).push(5).average
Stack.empty[Double].push(1).push(2).push(6).average
Stack.empty[String].push("1").push("2")
Stack.empty[Any].push("1").push(2)

Причем добавление .average в 3 или 4 строку вызывало ошибку компиляции. Инициализация стека через метод позволяет нам избежать некорректного конструирования стека, к примеру проинициализировав Stack[Int] с помощью GeneralStack[Int], который не позволит нам получить метод .average на стеке. Соответственно метод Stack.empty[T] должен уметь создавать правильный стек в зависимости от типа. Если бы у нас был только Numeric параметр - все было бы просто. Но у нас два варианта: Numeric и не Numeric. И для этого нам потребуется трюк с ambiguous implicits:

  1. Сначала определим тип для не равно:

    trait =!=[A, B]
implicit def neq[A, B] : A =!= B = null
implicit def neqAmbig1[A: Numeric]: A =!= Numeric[A] = null
implicit def neqAmbig2[A: Numeric]: A =!= Numeric[A] = null```

Тут метод neq будет вылавливать тип =!=[T, Numeric[T]] когда T на самом деле не Numeric. neqAmbig1 и neqAmbig2 будут блокировать нахождение имплисита для таких T которые Numeric

Далее нам нужен trait из которого мы можем полчить Numeric[T] когда он у нас есть, а также implicits которые нам его автоматически сгенерят:

trait NumericEvidence[A] {
  def getEvidence(): Option[Numeric[A]]
}
object NumericEvidence {
  implicit def getNumericEvidence[T](implicit ev: Numeric[T]): NumericEvidence[T] = () => Some(ev)
  implicit def noneEvidence[T: ClassTag](implicit ev: T =!= Numeric[T]): NumericEvidence[T] = () => None
}

В companion object у нас первый метод будет срабатывать для Numeric а второй будет срабатывать для не Numeric. Ну и реализация empty:

def empty[T: NumericEvidence]: Stack[T] = implicitly[NumericEvidence[T]].getEvidence()
  .fold[Stack[T]](new GeneralStack[T](Nil)){implicit ev =>
    new NumericStack[T](Nil, ev.zero, 0)
  }

И для полноты все вместе:

import scala.reflect.ClassTag

sealed trait Stack[T] {
  def push(element: T): Stack[T]
  def pop(): (Stack[T], T)
}

object Stack {
  private[Stack] case class GeneralStack[T](elements: List[T]) extends Stack[T] {
    def push(element: T): GeneralStack[T] = {
      new GeneralStack[T](element :: elements)
    }

    def pop(): (GeneralStack[T], T) = elements match {
      case head :: tail =>
        new GeneralStack[T](tail) -> head
      case _ => throw new Exception("Stack is empty")
    }
  }

  private[Stack] case class NumericStack[T: Numeric](elements: List[T], sum: T, count: Int) extends Stack[T] {
    def push(element: T): NumericStack[T] = {
      val newSum = implicitly[Numeric[T]].plus(sum, element)
      new NumericStack[T](element :: elements, newSum, count + 1)
    }

    def pop(): (NumericStack[T], T) = elements match {
      case head :: tail =>
        val newSum = implicitly[Numeric[T]].minus(sum, head)
        new NumericStack[T](tail, newSum, count - 1) -> head
      case _ => throw new Exception("Stack is empty")
    }
  }

  trait =!=[A, B]
  implicit def neq[A, B]: A =!= B = null
  implicit def neqAmbig1[A: Numeric]: A =!= Numeric[A] = null
  implicit def neqAmbig2[A: Numeric]: A =!= Numeric[A] = null

  trait NumericEvidence[A] {
    def getEvidence(): Option[Numeric[A]]
  }
  object NumericEvidence {
    implicit def getNumericEvidence[T](implicit ev: Numeric[T]): NumericEvidence[T] = () => Some(ev)
    implicit def noneEvidence[T: ClassTag](implicit ev: T =!= Numeric[T]): NumericEvidence[T] = () => None
  }

  def empty[T: NumericEvidence]: Stack[T] = implicitly[NumericEvidence[T]]
    .getEvidence()
    .fold[Stack[T]](new GeneralStack[T](Nil)) { implicit ev => new NumericStack[T](Nil, ev.zero, 0) }

  implicit class NumericFraStack[T: Fractional](base: Stack[T]) {
    def average: T = {
      base match {
        case NumericStack(_, sum, count) =>
          val c = implicitly[Fractional[T]].fromInt(count)
          implicitly[Fractional[T]].div(sum, c)
        case _ =>
          throw new Exception("Wrong type")
      }
    }
  }
  implicit class NumericIntStack[T: Integral](base: Stack[T]) {
    def average: T = {
      base match {
        case NumericStack(_, sum, count) =>
          val c = implicitly[Integral[T]].fromInt(count)
          implicitly[Integral[T]].quot(sum, c)
        case _ =>
          throw new Exception("Wrong type")
      }
    }
  }
}

Stack.empty[Int].push(1).push(2).push(5).average
Stack.empty[Double].push(1).push(2).push(6).average
Stack.empty[String].push("1").push("2")
Stack.empty[Any].push("1").push(2)
→ Ссылка

licensed under cc by-sa 3.0 with attribution.