Как в Scala обобщить Int и BigInt?

Question

[mayton2019]

Пример из книжки Степанова. Египетское умножение. Я реализовал для целых чисел (Int)

def half(a:Int) : Int = a / 2
def half(a:BigInt) : BigInt = a / 2

def odd(a:Int) : Boolean = a % 2 == 1
def odd(a:BigInt) : Boolean = a % 2 == 1

def mult_acc4(n:Int, a:Int, r:Int = 0) : Int = (odd(n), n) match {
  case (true, 1) => r + a
  case (true, _) => mult_acc4(half(n), a + a, r + a)
  case (_,_)     => mult_acc4(half(n), a + a, r)
}

Потом был интерес сделать в BigInt чтобы Египетское умножение себя хоть как-то показало на длинных числах.

def mult_acc5(n:BigInt, a:BigInt, r:BigInt = 0) : BigInt = (odd(n), n) match {
  case (true, 1) => r + a
  case (true, _) => mult_acc5(half(n), a + a, r + a)
  case (_,_)     => mult_acc5(half(n), a + a, r)
}

Здесь пришлось сделать еще две реализации для проверки нечетных odd() и для деления на 2 half().
После этого я стал искать обобщенную реализацию. Сделал интерфейс числа которое складывает и делит и прочее.
И получается что писанины у меня стало от этого только больше. И баги ООП - как тушение пожара. Фиксишь один - лезет
следующих два.

trait PolyNum[T] {
  def +(x:T) : T
  def half : T
  def odd : Boolean
  def one : T
}


// illegal trait inheritance: superclass AnyVal does not derive from trait PolyNum's superclass Object
case class X(v:BigInt) extends AnyVal with PolyNum[BigInt] {
  override def +(x:BigInt) : BigInt = v + x
  override def odd : Boolean = v % 2 == 1
  override def half : BigInt = v / 2
  override def one : BigInt = BigInt(1)
}

// TODO: Fix
def mult_acc6[T](n:PolyNum[T], a:PolyNum[T], r:PolyNum[T]) : PolyNum[T] = (n.odd, n) match {
  case (true, n.one) => r + a
  case (true, _) => mult_acc6(n.half, a + a, r + a)
  case (_,_)     => mult_acc6(n.half, a + a, r)
}

Чувсвтую что ошибаюсь. Вот где?
Как красиво и изящно обобщить операции над целым и над BigInt?

Comments

[Ерлан Ибраев]

Красиво фиг его знает.
У меня так получилось:

class Main {
 
  def half(a:Int) : Int = a / 2
  def half(a:BigInt) : BigInt = a / 2

  def odd(a:Int) : Boolean = a % 2 == 1
  def odd(a:BigInt) : Boolean = a % 2 == 1

  def odd[T](a: T): Boolean  =
    a match {
      case x: BigInt => odd(x)
      case x: Int => odd(x)
    }

  def half[T](a: T): T =
    a match {
      case x: Int => half(x).asInstanceOf[T]
      case x: BigInt => half(x).asInstanceOf[T]
    }

  def one[T](n:T): T =
    n match {
      case x: Int => 1.asInstanceOf[T]
      case x: BigInt => BigInt(1).asInstanceOf[T]
    }

  def sum[T](a: T, b:T): T =
    (a, b) match {
      case (x: Int, y: Int) => (x + y).asInstanceOf[T]
      case (x: BigInt, y: BigInt) => (x + y).asInstanceOf[T]
    }


  def mult_acc[T](n: T, a: T, r: T): T = {
    val odin = one(n)
    (odd(n), n) match {
      case (true, odin) => sum(r, a)
      case (true, _) => mult_acc(half(n), sum(a, a), sum(r, a))
      case (_, _) => mult_acc(half(n), sum(a, a), r)
    }
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    println("привет")
    val test = new Main
    println(test.mult_acc(BigInt(1),BigInt(3),BigInt(4)))
    println(test.mult_acc(1,3,4))
  }
}

[mayton2019]

Ерлан Ибраев, я понял. Ну это Haskell-like. А если мне надо будет потом добавить дробно-десятичное или рациональное - то придется весь код менять. А хотелось просто добавить еще один ... ээ класс? Тип?

[mayton2019]

Ну и оператор "+" хотелось сохранить.

[Ерлан Ибраев]

mayton2019,
например так :-)

trait PolyNum[T] {
  def +(x:PolyNum[T]) : PolyNum[T]
  def half : PolyNum[T]
  def odd : Boolean
  def one : PolyNum[T]
  def value: T
}

case class X(v:BigInt) extends PolyNum[BigInt] {
  override def +(x:PolyNum[BigInt]) : PolyNum[BigInt] = X(v + x.value)
  override def odd : Boolean = v % 2 == 1
  override def half : PolyNum[BigInt] = X(v / 2)
  override def one : PolyNum[BigInt] = X(BigInt(1))
  override def value: BigInt = v
}

case class Y(v:Int) extends PolyNum[Int] {
  override def +(x:PolyNum[Int]) : PolyNum[Int] = Y(v + x.value)
  override def odd : Boolean = v % 2 == 1
  override def half : PolyNum[Int] = Y(v / 2)
  override def one : PolyNum[Int] = Y(1)
  override def value: Int = v
}

def multi_acc[T](n: PolyNum[T], a: PolyNum[T], r: PolyNum[T]): PolyNum[T] = {
  val odin = n.one
  (n.odd, n) match {
    case (true, odin) => (r + a)
    case (true, _) => multi_acc(n.half, a + a, r + a)
    case (_, _) => multi_acc(n.half, a + a, r)
  }

}

object Main {
  def main(args: Array[String]): Unit = {
    println("привет")
    println(multi_acc(X(BigInt(1)),X(BigInt(3)),X(BigInt(4))).value)
    println(multi_acc(Y(1),Y(3),Y(4)).value)
  }
}

[mayton2019]

Ерлан Ибраев, спасибо. Я подумаю. Вобщем-то первый вариант вполне норм.

P.S. Да и умножение только 2 аргумента берет. Третий - аккумулятор. Поэтому Египетское умножение
по Степанову это такая форма:

multi_acc(X(BigInt(10000000000)),X(BigInt(300000000000))

[Ерлан Ибраев]

mayton2019, Так с аккумулятором вообще просто. Просто в в последний мой исходник добавляете функцию

def multi_acc[T](n: PolyNum[T], a: PolyNum[T]): PolyNum[T]

С условием выхода на функцию с тремя аргументами. Т.е. с инциализацией аккумулятора.

P.S. Это было по приколу первая программа на Scala :-)
Аналогично можно написать на kotlin

[mayton2019]

Ерлан Ибраев, вы молодец. Ваша первая программа лучше чем моя первая.

Answer 1

[sheerluck]

А чем просто генерики не подходят?
def mult_acc11[T](n:T, a:T, r:T = 0) : Int = ...

Comments

[mayton2019]

Вот так наверное?

def mult_acc11[T](n:T, a:T, r:T = 0) : T= ..
Не компилируется если подставлять Int или BigInt

[sheerluck]

import Integral.Implicits._

object Main {
 
  def half[T:Integral](a:T) : T = a / 2.asInstanceOf[T]
  def odd[T:Integral](a:T) : Boolean = a % 2.asInstanceOf[T] == 1.asInstanceOf[T]
  
  def mult_acc11[T:Integral](n:T, a:T, r:T = 0) : T = (odd(n), n) match {
    case (true, 1) => r + a
    case (true, _) => mult_acc11(half(n), a + a, r + a)
    case (_,_)     => mult_acc11(half(n), a + a, r)
  }
  
  def main(args: Array[String]): Unit = {
    def f(n: Int) = (BigInt(1) to BigInt(n)).product
    println(mult_acc11(7,5))
  }
}

[mayton2019]

sheerluck, Хм... Integral, дайте проверю.

[mayton2019]

Не летает. С 2 аргументами - требует evidence в фазе компилляции. Если третий дефолтный указать то получаем ошибку рантайма.

scala> object Main {
     |
     |   def half[T:Integral](a:T) : T = a / 2.asInstanceOf[T]
     |   def odd[T:Integral](a:T) : Boolean = a % 2.asInstanceOf[T] == 1.asInstanceOf[T]
     |
     |   def mult_acc11[T:Integral](n:T, a:T, r:T = 0) : T = (odd(n), n) match {
     |     case (true, 1) => r + a
     |     case (true, _) => mult_acc11(half(n), a + a, r + a)
     |     case (_,_)     => mult_acc11(half(n), a + a, r)
     |   }
     |
     |   def main(args: Array[String]): Unit = {
     |     println(mult_acc11(7, 5))
     |
     |     // println(mult_acc11(BigInt(700000000), BigInt(500000000)))
     |     // missing argument for parameter evidence$3 of method mult_acc11 in object Main: (implicit evidence$3: Integral[Matchable]): Matchable
     |
     |     println(mult_acc11(BigInt(700000000), BigInt(500000000), BigInt(0)))
     |   }
     | }
// defined object Main

scala> Main.main(Array())
35
java.lang.ClassCastException: class java.lang.Integer cannot be cast to class scala.math.BigInt (java.lang.Integer is in module java.base of loader 'bootstrap'; scala.math.BigInt is in unnamed module of loader java.net.URLClassLoader @667e34b1)
  at scala.math.Numeric$BigIntIsIntegral$.rem(Numeric.scala:49)
  at scala.math.Integral$IntegralOps.$percent(Integral.scala:24)
  at rs$line$11$Main$.odd(rs$line$11:4)
  at rs$line$11$Main$.mult_acc11(rs$line$11:6)
  at rs$line$11$Main$.main(rs$line$11:18)
  ... 34 elided

[sheerluck]

import Integral.Implicits._

object Main {
 
  def half[T:Integral](a:T) : T = a match {
    case i: Int => (i / 2).asInstanceOf[T]
    case b: BigInt => (b / 2).asInstanceOf[T]
  }
  
  
  def odd[T:Integral](a:T) : Boolean = a match {
    case i: Int => i % 2 == 1
    case b: BigInt => b % 2 == 1
  }
  
  def mult_acc11[T:Integral](n:T, a:T, r:T = 0) : T = (odd(n), n) match {
    case (true, 1) => r + a
    case (true, _) => mult_acc11(half(n), a + a, r + a)
    case (_,_)     => mult_acc11(half(n), a + a, r)
  }
  
  def main(args: Array[String]): Unit = {
    println(mult_acc11(BigInt(700000000), BigInt(500000000), BigInt(0)))
  }
}

[mayton2019]

Шикарно.

scala> Main.main(Array())
350000000000000000

Собсно откуда у меня проблема пошла. Есть сет алгортмов на С++ написанных мной еще лет 15 назад. Игры с целочисленной арифметикой. Генерация простых и прочее. И возникло у меня желание с минимальными изменениями перенести это все в диапазон Int/Long/BigInt.

Я надеялся что перегруженные операции помогут. Но вот здесь odd и half выглядят достаточно костыльно. Ну тоесть эффект - "ну нормуль" наблюдается. Но чтобы эффект ура-ура... такого нет.

Впрочем я не буду к вам приставать. Я думаю на этот топик уже ответ получен. Его можно и закрыть.