Можно ли написать неизменный двусвязный список?

Question

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

Предположим, что список A:: B, во время создания, A должен знать о B, но B также должен знать о A. Я делал это в Scala, поэтому я не уверен, специфичен ли он для Scala, но я не могу представить, как это будет работать.

Я не ищу замену, потому что мне это ни для чего не нужно, мне просто любопытно.

Answer 1

Да, это возможно. Обычно это не делается, потому что, в отличие от односвязного списка, в двусвязном списке нет подструктур, которые можно было бы использовать повторно, например, при удалении одного элемента. Кроме того, такой список, кажется, не делает ничего, что является неизменным Vector не могу сделать.

Тем не менее, давайте запишем это, потому что это весело.

Упрощенная задача: круговой двухэлементный "список"

В качестве разминки рассмотрим упрощенную проблему: круговой двухэлементный "список" с двумя узлами, ссылающимися друг на друга:

case class HalfRing(val value: Int)(otherHalf: => HalfRing) {
  def next = otherHalf
}

object HalfRing {
  def fullRing(a: Int, b: Int): HalfRing = {
    lazy val ha: HalfRing = HalfRing(a){hb}
    lazy val hb: HalfRing = HalfRing(b){ha}
    ha
  }
}

Это действительно работает, и мы можем построить эту небольшую двухузловую структуру данных и выполнить ее по кругу в течение нескольких миллионов итераций:

var r = HalfRing.fullRing(42, 58)
for (i <- 0 until 1000000) {
  r = r.next
  if (i % 100001 == 0) println(r.value)
}

Выход:

58
42
58
42
58
42
58
42
58
42

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

---

Неизменяемый двойной список

Я решил представить список узлами, связанными двойными ссылками, и двумя явными Nil-элементы на обоих концах:

sealed trait DLL[+A] extends (Int => A)
case class LeftNil[+A]()(n: => DLL[A]) extends DLL[A] {
  def next = n
  def apply(i: Int) = next(i)
}
case class RightNil[+A]()(p: => DLL[A]) extends DLL[A] {
  def prev = p
  def apply(i: Int) = 
    throw new IndexOutOfBoundsException("DLL accessed at " + i)
}
case class Cons[+A](value: A)(p: => DLL[A], n: => DLL[A]) extends DLL[A] {
  def next = n
  def prev = p
  def apply(i: Int) = if (i == 0) value else next(i - 1)
}

apply-part в основном не имеет значения, я добавил его только для того, чтобы потом можно было просмотреть и распечатать содержимое. Интересный вопрос: как мы можем на самом деле создать такой список? Вот способ конвертировать один связанный список в двойной связанный список:

object DLL {
  def apply[A](sll: List[A]): DLL[A] = {
    def build(rest: List[A]): (=> DLL[A]) => DLL[A] = rest match {
      case Nil => RightNil[A]() _
      case h :: t => {
        l => {
          lazy val r: DLL[A] = build(t){c}
          lazy val c: DLL[A] = Cons(h)(l, r)
          c
        }
      }
    }
    lazy val r: DLL[A] = build(sll){l}
    lazy val l: DLL[A] = LeftNil(){r}
    l
  }
}

То, что происходит здесь, по сути та же самая хитрость, что и с кольцом из двух элементов выше, но повторяется несколько раз. Мы просто продолжаем соединять части таким же образом, как мы соединяли два полукольца, за исключением того, что здесь мы сначала соединяем маленькие Cons-элементы к длинным хвостам списка, и, наконец, присоединиться к LeftNil с первым Cons,

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

val dll = DLL((42 to 100).toList)

println((1 to 20).map(dll))

@annotation.tailrec 
def bounceBackAndForth(
  dll: DLL[Int], 
  maxIters: Int, 
  direction: Int = +1
): Unit = {
  if (maxIters <= 0) println("done")
  else dll match {
    case ln: LeftNil[Int] => bounceBackAndForth(ln.next, maxIters - 1, +1)
    case rn: RightNil[Int] => bounceBackAndForth(rn.prev, maxIters - 1, -1)
    case c: Cons[Int] => {
      if (maxIters % 100003 == 0) println(c.value)
      if (direction < 0) {
        bounceBackAndForth(c.prev, maxIters - 1, -1)
      } else {
        bounceBackAndForth(c.next, maxIters - 1, +1)
      }
    }
  }
}

bounceBackAndForth(dll, 1000000)

// cs_XIIIp4

Замечание: я не нахожу рекурсивный build- метод особенно интуитивный, я не мог записать его напрямую, не набросав на листе бумаги несколько минут. Если честно, я все еще немного удивляюсь каждый раз, когда это работает.