Как распечатать рекурсивные значения в Scala? - PullRequest
Новая
       59

Как распечатать рекурсивные значения в Scala?

2 голосов
/ 03 августа 2020

Я пишу Lisp на Scala. 

sealed trait Val

final case class Atom(name: String) extends Val

final case object Null extends Val

final class Cons(a: Val, d: => Val) extends Val {
  override def toString(): String = "Cons(" + a.toString() + "," + d.toString() + ")"
}

Как мне правильно напечатать рекурсивные Val s? Пример: 

lazy val lst:Val = new Cons(Atom("a"), {lst})
lst.toString()

Я хочу, чтобы результат был #1=Cons(Atom("a"), #1).

Ответы [ 2 ]

2 голосов
/ 05 августа 2020

У меня есть опыт применения круговой нотации, но в C.

Во-первых, существует более одного подхода.

Вы должны сделать шаг назад и подумать: всегда ли объекты движутся для печати в текст с использованием toString? То есть, не планируете ли вы иметь потоки ввода-вывода и способ печати объектов в потоке, а не преобразование их в строку?

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

При реализации круговой нотации можно делать что-то в различные способы. Ключевая проблема заключается в том, что вы не хотите ставить метку numeri c на все, независимо от того, нужна она или нет, потому что это будет выглядеть некрасиво. Например: 

#1=(#2=(a b) #3=(c d) e) ;; no circularity or substructure sharing!

Но в тот момент, когда ваш принтер считает наиболее удобным начать излучение объекта, он должен знать: выпускать этикетку или нет?

Еще один момент Считайте, что круговое обозначение дорого. Вот почему ANSI Lisp указывает специальную переменную *print-circle* для его включения, которая по умолчанию отключена. Вероятно, будет хорошей идеей реализовать такой переключатель. должен работать, даже когда используются эти пользовательские методы печати. Это важно, потому что в отсутствие пользовательских методов ваш принтер может легко передать себе произвольный объект контекста при его рекурсии. Объект может указывать на то, что включена круговая нотация (нет необходимости постоянно проверять переменную Dynami c, и он может содержать таблицу ha sh для меток и прочего). Если принтер вызывает пользовательский метод печати, который может вызывать обратно в принтер, этот красивый внутренний контекст не может быть передан: он не является частью API.

В любом случае, простой алгоритм, который работает, - это сначала пройдите по объекту, который нужно напечатать, и постройте таблицу ha sh всех составляющих его объектов, которые «подходят для круга». Например, целые числа fixnum или интернированные символы не являются; не добавляйте их в ha sh. В ha sh (который я предполагаю здесь в стиле Lisp ha sh) вы можете связать nil с объектом, когда он впервые представлен. Если виден дубликат объекта, nil переключается на t. Конечно, всякий раз, когда вы обнаруживаете, что посещаемый объект уже находится в ha sh, вы не будете его повторять. Это приведет к поражению всего упражнения. После создания ha sh вы обращаетесь к нему во время печати. Когда вы собираетесь напечатать объект, соответствующий требованиям круга, вы сначала ищите его в ha sh. Если ha sh имеет t, вы заменяете это t значением счетчика меток, выводите текст #<counter>=, где <counter> - значение счетчика меток, а затем распечатываете объект. Счетчик увеличивается. Если ha sh связывает объект с целым числом, это означает, что вы уже напечатали нотацию #<counter>= для этого объекта. Это просто ссылка на этот объект: просто выведите #<that integer>#, чтобы представить этот объект, и все готово.

Это основная идея c. Если вы когда-нибудь решите реализовать нотацию плоского списка с точкой, вам понадобится следующий logi c. Например, рассмотрим круговой список #1=(a b c . #1#). Если принтер не обращает внимания на округлость, он просто печатает (a b c a b c a b c ... навсегда или до тех пор, пока не будет достигнут установленный предел длины списка. Это просто цикл, пока итератор cdr не попадет в атом. В круговом режиме принтер при отображении плоского списка должен следить за попаданием итератора cdr в круговой ha sh. Если это так, то он должен напечатать конечную точку и обозначение, закрыть скобку и закончить l oop. Регистр #= может находиться в этой позиции: (a b c . #1=(d e . #1#)). Положительное попадание ha sh по существу рассматривается как завершающий атом.

1 голос
/ 03 августа 2020

Во-первых, это двоичное дерево не список , так как оба параметра Cons могут быть Cons: 

new Cons(new Cons(Atom("a"), Null), new Cons(Atom("b"),Null))

Вы можете обрабатывать самореферентные объекты с помощью теста: 

final class Cons(a: Val, d: => Val) extends Val {
 override def toString =
    if (d == this) {
      "Cons(" + a.toString + ", self)"
    } else {
      "Cons(" + a.toString + "," + d.toString + ")"
    }
}

Но взаимно-ссылочные объекты по-прежнему остаются проблемой: 

lazy val lst1:Val = new Cons(Atom("a"), lst2)
lazy val lst2 = new Cons(Atom("a"), new Cons(Atom("b"), lst1))

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

...