Basi c реализация структуры данных List в Scala

Question

Я изучаю Scala, и в книге, которую я читаю ( Функциональное программирование в Scala), я натолкнулся на пример пользовательской реализации List в Scala, которая выглядит так:

sealed trait MyList[+A]
case object MyNil extends MyList[Nothing]
case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A]
object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil
    else Cons(as.head, apply(as. tail: _*))
}

Я хотел бы расширить MyList, чтобы добавить следующую функциональность:

1. добавить метод tail, который возвращает все элементы MyList экземпляр без первого, например val x = MyList(1,2,3); x.tail == MyList(2,3).

2. Добавить метод sum, который применим только тогда, когда MyList содержит Int с (или даже лучше для всех чисел c типов). Например, val x = MyList(1,2,3); x.sum == 6

Идея над двумя вопросами состоит в том, чтобы понять: (1) как взаимодействовать с экземпляром моего класса и (2) как использовать полиморфизм в ситуации, подобной это. После некоторых поисков я даже не знаю, как начать с этих проблем, поэтому я задаю этот вопрос.

Буду признателен за любые советы. Большое спасибо!

ОБНОВЛЕНИЕ:

Несколько обновлений:

Во-первых, я хотел бы отметить, что решение проблем программирования в курс функционального программирования, о котором я упоминал ранее, можно найти здесь , однако я ищу что-то немного отличное от того, о чем просит автор.

Мне удалось найти ответ на мой первый вопрос «как я могу использовать tail на моем экземпляре, например, MyList(1,2,3).tail?». Чтобы решить эту проблему, мне пришлось изменить исходную черту следующим образом:

sealed trait MyList[+A] {
  def tail: MyList[A] = MyList.tail(this)
}

Я не уверен, что это лучший способ делать то, что я хочу, но это работает. Если у кого-то есть лучшие предложения, пожалуйста, дайте мне знать.

Вторая часть сложнее. Я хотел добавить следующее в ту же черту:

def sum[Int]: MyList[Int] = MyList.sum(this)

Но IntelliJ жалуется на тип this, равный A, и мне нужно условно применить это к this типа Int.

Другая альтернатива заключается в следующем:

def sum: Int = this match {
    case x: MyList[Int] => MyList.sum(x)
 }

Но что, если мы хотим создать другую реализацию для String, которая также будет возвращать String? Это не может быть правильным решением, и я еще не нашел его. Пожалуйста, помогите:)

Answer 1

.tail

Замечу, что в вашем классе Cons уже есть член publi c tail. Я хотел бы начать там и сделать его универсальным ...

sealed trait MyList[+A] {
  def tail: MyList[A]
}

... и добавить реализацию MyNil.

case object MyNil extends MyList[Nothing] {
  def tail: MyList[Nothing] = 
    throw new java.lang.UnsupportedOperationException("tail of empty list")
}

Вот как стандарт библиотека List обрабатывает хвост пустого списка. Другим, возможно, более мягким вариантом будет возвращение this, так что хвост пустого MyList будет просто пустым MyList.

Оставив class Cons и object MyList без изменений, мы получим ожидаемые результаты.

MyList('s','h','o','w').tail  //res0: MyList[Char] = Cons(h,Cons(o,Cons(w,MyNil)))
MyList(9).tail.tail           //java.lang.Unsupported...

.sum

Это немного сложнее. Мы хотим, чтобы каждый вызов .sum компилировал только , если элементы имеют суммируемый тип, такой как Int. Scala способ добиться этого, требующий, чтобы сайт вызова предоставил неявные "доказательства" того, что тип элемента приемлем.

sealed trait MyList[+A] {
  def sum(implicit ev : A =:= Int) : Int  //can sum only if A is Int
}

Увы, это не скомпилируется, потому что MyList является ковариантным для A, но, будучи типом переданного параметра, ставит A в противоположную позицию.

Ошибка: ковариантный тип A встречается в инвариантной позиции в типе A =: = Int значения ev

К счастью, есть исправление: используйте параметр другого типа, связанный с A, но не ограниченный его ковариантным отношением.

sealed trait MyList[+A] {
  def sum[B >: A](implicit ev : B =:= Int) : Int = 0  //default behavior
}

case object MyNil extends MyList[Nothing] { ... //unchanged

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev :B =:= Int) : Int = head + tail.sum[B]
}

object MyList { ... //unchanged

MyList(23,31,12).sum   //res0: Int = 66
MyList("as","is").sum  //won't compile

Числовой [A]

Хорошо, это работает для Int, но было бы больно делать то же самое для каждого суммируемого типа. К счастью, стандартная библиотека предлагает класс типов Numeric, который предоставляет некоторые базовые значения c (zero и one) и операции (plus(), minus(), times(), et c.) Для всех цифры c печатаются под зонтиком (Short, Long, Float, et c.).

Итак, все вместе:

sealed trait MyList[+A] {
  val tail: MyList[A]
  def sum[B >: A](implicit ev : Numeric[B]): B = ev.zero
}

case object MyNil extends MyList[Nothing] {
  val tail: MyList[Nothing] = this
}

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev : Numeric[B]): B = ev.plus(head, tail.sum[B])
}

object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil else Cons(as.head, apply(as.tail: _*))
}