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

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

0 голосов
/ 22 мая 2018

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

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

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

1 Ответ

0 голосов
/ 22 мая 2018

Да, это возможно.Обычно это не делается, потому что, в отличие от односвязного списка, в двусвязном списке нет подструктур, которые можно было бы использовать повторно, например, при удалении одного элемента.Более того, такой список, похоже, не делает ничего такого, чего не может сделать неизменный 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

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

Неизменная двойная связьlist

Я решил представить список узлами, связанными двойными ссылками, и двумя явными 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-часть в основном не имеет значения, я добавил ее только для проверкиt и распечатать содержимое позже.Интересный вопрос: как мы можем на самом деле создать такой список?Вот способ конвертировать один связанный список в двойной связанный список: 

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 -метод особенно интуитивно понятным, я не мог записать его напрямую, не набросав на листе бумаги несколько минут.Честно говоря, я все еще немного удивляюсь каждый раз, когда это работает.

...