Сложность конкатенации связанных списков - PullRequest
Новая
       22

Сложность конкатенации связанных списков

0 голосов
/ 04 июня 2018

Я все еще довольно плохо знаком с функциональным программированием и экспериментирую с алгебраическими типами данных.Я реализовал LinkedList следующим образом: 

sealed abstract class LinkedList[+T]{
  def flatMap[T2](f: T => LinkedList[T2]) = LinkedList.flatMap(this)(f)
  def foreach(f: T => Unit): Unit = LinkedList.foreach(this)(f)
}

final case class Next[T](t: T, linkedList: LinkedList[T]) extends LinkedList[T]
case object Stop extends LinkedList[Nothing]

object LinkedList{
  private def connect[T](left: LinkedList[T], right: LinkedList[T]): LinkedList[T] = left match {
    case Stop => right
    case Next(t, l) => Next(t, connect(l, right))
  }

  private def flatMap[T, T2](list: LinkedList[T])(f: T => LinkedList[T2]): LinkedList[T2] = list match {
    case Stop => Stop
    case Next(t, l) => connect(f(t), flatMap(l)(f))
  }

  private def foreach[T](ll: LinkedList[T])(f: T => Unit): Unit = ll match {
    case Stop => ()
    case Next(t, l) =>
      f(t)
      foreach(l)(f)
  }
}

Дело в том, что я хотел измерить сложность операции flatMap.

Сложность flatMap равна O(n), где n - это длина списка flatMap (насколько я могу судить по индукции).

Вопрос в том, как составить список таким образом, чтобы конкатенация имела постоянную сложность?Какой тип class extends LinkedList мы должны разработать, чтобы достичь этого?Или, может быть, каким-то другим способом?

1 Ответ

0 голосов
/ 04 июня 2018

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

Я неПосмотрите, как сделать это с неизменными узлами, поскольку изменение того, что следует за хвостовым узлом, требует изменения всего перед ним.Чтобы получить постоянную конкатенацию с неизменяемыми структурами данных, вам нужно нечто иное, чем простой связанный список.

...